【問題描述】[中等]

給你一個整數數組 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. 暴力法

時間復雜度：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. 二分法

時間復雜度：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 的閾值 thresholdif (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);} }

時間復雜度：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 的閾值 thresholdif (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)

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-/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第1300题][转变数组后最接近目标值的数组和][前缀和][二分法][暴力]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。