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

Author Avatar
清水雅然君 06月 14,2020

题目地址
个人博客地址

题目描述

给你一个整数数组 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;