[Leedcode][JAVA][第1300题][转变数组后最接近目标值的数组和][前缀和][二分法][暴力]

秒速五厘米 2023-02-17 12:29 14阅读 0赞

#### 【问题描述】\[中等\] ####

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

#### 【解答思路】 ####

###### 1. 暴力法 ######

![在这里插入图片描述][20200614102522384.png]  
**时间复杂度：O(N^2) 空间复杂度：O(1)**

class Solution { 
        public int findBestValue(int[] arr, int target) { 
            int min = Integer.MAX_VALUE;
            int num = target/arr.length, minIndex = num;
            
            for (int i = num; i < target; i++) { 
                int sum = 0;
                for (int j = 0; j < arr.length; j++) { 
                    if (arr[j] > i)   sum += i;
                    else    sum += arr[j];
                }
                
                if (Math.abs(target-sum) < min) { 
                    min = Math.abs(target-sum);
                    minIndex = i;
                } else  break;
            }
            
            return minIndex;
        }
    }

###### 2. 二分法 ######

![在这里插入图片描述][20200614102641996.png]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]

![在这里插入图片描述][20200614103823734.png]

**时间复杂度：O(NlogN) 空间复杂度：O(1)**

public class Solution { 
    
        public int findBestValue(int[] arr, int target) { 
            int left = 0;
            int right = 0;
            // 注意：
            for (int num : arr) { 
                right = Math.max(right, num);
            }
    
            while (left < right) { 
                int mid = left + (right - left) / 2;
                int sum = calculateSum(arr, mid);
                // 计算第 1 个使得转变后数组的和大于等于 target 的阈值 threshold
                if (sum < target) { 
                    // 严格小于的一定不是解
                    left = mid + 1;
                } else { 
                    right = mid;
                }
            }
    
            // 比较阈值线分别定在 left - 1 和 left 的时候与 target 的接近程度
            int sum1 = calculateSum(arr, left - 1);
            int sum2 = calculateSum(arr, left);
            if (target - sum1 <= sum2 - target) { 
                return left - 1;
            }
            return left;
        }
    
        private int calculateSum(int[] arr, int threshold) { 
            int sum = 0;
            for (int num : arr) { 
                sum += Math.min(num, threshold);
            }
            return sum;
        }
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 2, 3, 5};
            int target = 11;
            Solution solution = new Solution();
            int res = solution.findBestValue(arr, target);
            System.out.println(res);
        }
    }

![在这里插入图片描述][20200614103756529.png]  
**时间复杂度：O(NlogN) 空间复杂度：O(1)**

public class Solution { 
    
        public int findBestValue(int[] arr, int target) { 
            int left = 0;
            int right = 0;
            // 注意：
            for (int num : arr) { 
                right = Math.max(right, num);
            }
    
            while (left < right) { 
                int mid = left + (right - left + 1) / 2;
                int sum = calculateSum(arr, mid);
                // 计算最后 1 个使得转变以后数组的和小于等于 target 的阈值 threshold
                if (sum > target) { 
                    // 大于等于的就不是解，threshold 太大了，下一轮搜索区间是 [left, mid - 1]
                    right = mid - 1;
                } else { 
                    // 下一轮搜索区间是 [mid, right]
                    left = mid;
                }
            }
    
            // 比较阈值线分别定在 left 和 left + 1 的时候与 target 的接近程度
            int sum1 = calculateSum(arr, left);
            int sum2 = calculateSum(arr, left + 1);
            // 注意：这里必须加绝对值，因为有可能出现 sum1 == sum2 < target 的情况
            if (Math.abs(target - sum1) <= Math.abs(sum2 - target)) { 
                return left;
            }
            return left + 1;
        }
    
        private int calculateSum(int[] arr, int threshold) { 
            int sum = 0;
            for (int num : arr) { 
                sum += Math.min(num, threshold);
            }
            return sum;
        }
    
        public static void main(String[] args) { 
            int[] arr = new int[]{ 2, 3, 5};
            int target = 11;
            Solution solution = new Solution();
            int res = solution.findBestValue(arr, target);
            System.out.println(res);
        }
    }

#### 【总结】 ####

###### 1.巧妙计算前缀和 ######

int[] prefix = new int[n + 1];
            for (int i = 1; i <= n; ++i) { 
                prefix[i] = prefix[i - 1] + arr[i - 1];
            }

###### 2. binarySearch(Object\[\], Object key) ######

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]

###### 3.排除法二分总结 ######

参考链接https://blog.csdn.net/dadongwudi/article/details/105345157

转载链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/er-fen-cha-zhao-by-liweiwei1419-2/

参考链接：https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target/solution/fen-duan-zhi-hou-bao-li-cha-zhao-guan-fang-shu-ju-/

[20200614102522384.png]: https://img-blog.csdnimg.cn/20200614102522384.png
[20200614102641996.png]: https://img-blog.csdnimg.cn/20200614102641996.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200614102705957.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200614102805255.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70
[20200614103823734.png]: https://img-blog.csdnimg.cn/20200614103823734.png
[20200614103756529.png]: https://img-blog.csdnimg.cn/20200614103756529.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200614105116735.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk=,size_16,color_FFFFFF,t_70