跳转至

1300. 转变数组后最接近目标值的数组和

来源第 16 场双周赛 Q2难度中等分数1606

题目描述

给你一个整数数组 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 <= arr.length <= 10^4
  • 1 <= arr[i], target <= 10^5

解法

方法一：排序 + 前缀和 + 二分查找 + 枚举

思考

若对每个候选 \(\textit{value}\) 都扫描一遍数组求转变后的和，则复杂度为 \(O(n \times M)\)。其中 \(n \le 10^4\)、 \(M \le 10^5\)，难以稳定通过。

转变后的和只取决于「不超过 \(\textit{value}\) 的部分原样保留、超过的部分一律改成 \(\textit{value}\)」。将数组排序后，分界点是一段前缀，可用二分定位，前缀和一次算出保留部分。因此按 \(0\) 到 \(\max(\textit{arr})\) 枚举 \(\textit{value}\)，每次 \(O(\log n)\) 求转变和并维护与 \(\textit{target}\) 的最小绝对差；差值相同时取更小的 \(\textit{value}\)。

我们注意到，题目中要把所有大于 \(\textit{value}\) 的值变成 \(\textit{value}\)，并且求和，因此我们可以考虑先对数组 \(\textit{arr}\) 进行排序，然后求出前缀和数组 \(s\)，其中 \(s[i]\) 表示数组前 \(i\) 个元素之和。

接下来，我们可以从小到大枚举所有 \(\textit{value}\) 值，对于每个 \(\textit{value}\)，我们可以通过二分查找找到数组中第一个大于 \(\textit{value}\) 的元素的下标 \(i\)，此时数组中大于 \(\textit{value}\) 的元素个数为 \(n - i\)，因此数组中小于等于 \(\textit{value}\) 的元素个数为 \(i\)，此时数组中小于等于 \(\textit{value}\) 的元素之和为 \(s[i]\)，数组中大于 \(\textit{value}\) 的元素之和为 \((n - i) \times \textit{value}\)，因此数组中所有元素之和为 \(s[i] + (n - i) \times \textit{value}\)。如果 \(s[i] + (n - i) \times \textit{value}\) 与 \(\textit{target}\) 的差的绝对值小于当前的最小差值 diff，则更新 diff 和 ans。

枚举完所有 \(\textit{value}\) 后，即可得到最终答案 ans。

时间复杂度 \(O(n \log n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为数组 \(\textit{arr}\) 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findBestValue(self, arr: list[int], target: int) -> int:
        arr.sort()
        s = list(accumulate(arr, initial=0))
        ans, diff = 0, inf
        for value in range(max(arr) + 1):
            i = bisect_right(arr, value)
            d = abs(s[i] + (len(arr) - i) * value - target)
            if diff > d:
                diff = d
                ans = value
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int findBestValue(int[] arr, int target) {
        Arrays.sort(arr);
        int n = arr.length;
        int[] s = new int[n + 1];
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + arr[i];
            mx = Math.max(mx, arr[i]);
        }
        int ans = 0, diff = 1 << 30;
        for (int value = 0; value <= mx; ++value) {
            int i = search(arr, value);
            int d = Math.abs(s[i] + (n - i) * value - target);
            if (diff > d) {
                diff = d;
                ans = value;
            }
        }
        return ans;
    }

    private int search(int[] arr, int x) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > x) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int findBestValue(vector<int>& arr, int target) {
        sort(arr.begin(), arr.end());
        int n = arr.size();
        int s[n + 1];
        s[0] = 0;
        int mx = 0;
        for (int i = 0; i < n; ++i) {
            s[i + 1] = s[i] + arr[i];
            mx = max(mx, arr[i]);
        }
        int ans = 0, diff = 1 << 30;
        for (int value = 0; value <= mx; ++value) {
            int i = upper_bound(arr.begin(), arr.end(), value) - arr.begin();
            int d = abs(s[i] + (n - i) * value - target);
            if (diff > d) {
                diff = d;
                ans = value;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func findBestValue(arr []int, target int) (ans int) {
    sort.Ints(arr)
    n := len(arr)
    s := make([]int, n+1)
    mx := slices.Max(arr)
    for i, x := range arr {
        s[i+1] = s[i] + x
    }
    diff := 1 << 30
    for value := 0; value <= mx; value++ {
        i := sort.SearchInts(arr, value+1)
        d := abs(s[i] + (n-i)*value - target)
        if diff > d {
            diff = d
            ans = value
        }
    }
    return
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

评论