Question

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

English Version

题目描述

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

解法

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

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

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

枚举完所有 value 后，即可得到最终答案 ans。

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

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

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;
  }
}

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;
  }
};

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
}