每日题解:LeetCode 1300. 转变数组后最接近目标值的数组和

题目地址
个人博客地址

题目描述

给你一个整数数组 arr 和一个目标值 target ,请你返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target (最接近表示两者之差的绝对值最小)。

如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。

请注意,答案不一定是 arr 中的数字。

示例 1:

输入:arr = [4,9,3], target = 10
输出:3
解释:当选择 value 为 3 时,数组会变成 [3, 3, 3],和为 9 ,这是最接近 target 的方案。
示例 2:

输入:arr = [2,3,5], target = 10
输出:5
示例 3:

输入:arr = [60864,25176,27249,21296,20204], target = 56803
输出:11361

解法

java

public class Solution {
    public int findBestValue(int[] arr, int target) {
        int sum=0,maxNum=arr[0];
        for (int a: arr) {
            if(a>maxNum) maxNum=a;
            sum+=a;
        }
        if(sum<=target) return maxNum;
        int left=0;
        int right=maxNum;
        while (left<=right){
            int mid=(left+right)>>1;
            int temp= getSum(arr,mid);
            if(temp-target==0) return mid;
            else if(temp<target) left=mid+1;
            else right=mid-1;
        }
  if(Math.abs(get_sum(arr,left)-target)<Math.abs(get_sum(arr,right)-target)) return left;
        else 
            return right;
    }
    public int getSum(int [] arr, int value){
        int sum=0;
        for (int a: arr) {
            if(a>value) sum+=value;
            else sum+=a;
        }
        return sum;
    }
}

解题思路

二分法

总结题目的要求。
如果原数组的和SUM小于等于target,之间返回数组的最大值便可以了,因为无论怎么调整数组的值,都不会出现和大于target。

 int sum=0,maxNum=arr[0];
        for (int a: arr) {
            if(a>maxNum) maxNum=a;
            sum+=a;
        }
        if(sum<=target) return maxNum;

如果原数组的和大于target,这里我们便需要在0~最大值maxNum中,需要一个value使得数组的和SUM最接近 target。
1.先实现获取sum的方法

  public int getSum(int [] arr, int value){
        int sum=0;
        //题目要求所有大于 value 的值变成 value,计算时取value值便可以了
        for (int a: arr) {
            if(a>value) sum+=value;
            else sum+=a;
        }
        return sum;
    }

2.寻找value
使用二分法,需要一个value,使得

        int left=0;
        int right=maxNum;
        while (left<=right){
            int mid=(left+right)>>1;
            int temp= getSum(arr,mid);
            if(temp-target==0) return mid;
            //取得一个和接近target的值
            else if(temp<target) left=mid+1;
            else right=mid-1;
        }

如果正好,mid的计算的值等于target。我们返回mid,不满足时,退出的条件为left>right,此时value取值left是一个数组和sum(arr)大于并且接近target的值,value取值right,是一个数组和sum(arr)小于并且接近target的值

value=right,sum(arr) < target 无法确定left和right谁更接近target,再求和取和target的差的绝对值进行比较
  if(Math.abs(get_sum(arr,left)-target)<Math.abs(get_sum(arr,right)-target)) return left;
 else 
 return right;
最近的文章

每周源码:如何实现ArrayList(分析ArrayList的源码)

@TOCJava集合(Collection)类是我们在工作中运用最多的、最频繁的类。并且集合可以动态扩容。方便开发需求。集合类通常存在于java.util包中,主要由Collection和Map两个体系构成。Collection主要有三个子接口,分别为List(列表)、Set(集)、Queue(队列…

继续阅读
更早的文章

每日题解:LeetCode 15. 三数之和

题目地址个人博客地址题目描述给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。注意:答案中不可以包含重复的三元组。示例:给定数组 nums = [-1, 0, 1, 2, -1, -4…

继续阅读