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

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

  • 标签:数组、二分查找、排序
  • 难度:中等

题目大意 #

给你一个整数数组 arr 和一个目标值 target

要求:返回一个整数 value ,使得将数组中所有大于 value 的值变成 value 后,数组的和最接近 target(最接近表示两者之差的绝对值最小)。如果有多种使得和最接近 target 的方案,请你返回这些整数中的最小值。

注意:答案 value 不一定是 arr 中的数字。

解题思路 #

题目可以理解为:在 [0, max(arr)] 的区间中,查找一个值 value。使得「转变后的数组和」与 target 最接近。

  • 转变规则:将数组中大于 value 的值变为 value

[0, max(arr)] 的区间中,查找一个值 value 可以使用二分查找答案的方式减少时间复杂度。但是这个最接近 target 应该怎么理解,或者说怎么衡量接近程度。

最接近 target 的肯定是数组和等于 target 的时候。不过更可能是出现数组和恰好比 target 大一点,或数组和恰好比 target 小一点。我们可以将 target 上下两个值相对应的数组和与 target 进行比较,输出差值更小的那一个 value

在根据查找的值 value 计算数组和时,也可以通过二分查找方法查找出数组刚好大于等于 value 元素下标。还可以根据事先处理过的前缀和数组,快速得到转变后的数组和。

最后输出使得数组和与 target 差值更小的 value

整个算法步骤如下:

  • 先对数组排序,并计算数组的前缀和 pre_sum
  • 通过二分查找在 [0, arr[-1]] 中查找使得转变后数组和刚好大于等于 target 的值 value
  • 计算 value 对应的数组和 sum_1,以及 value - 1 对应的数组和 sum_2。并分别计算与 target 的差值 diff_1diff_2
  • 输出差值小的那个值。

代码 #

 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
36
37
38
39
40
41
class Solution:
    # 计算 value 对应的转变后的数组
    def calc_sum(self, arr, value, pre_sum):
        size = len(arr)
        left, right = 0, size - 1
        while left < right:
            mid = left + (right - left) // 2
            if arr[mid] < value:
                left = mid + 1
            else:
                right = mid

        return pre_sum[left] + (size - left) * value

    # 查找使得转变后的数组和刚好大于等于 target 的 value
    def binarySearchValue(self, arr, target, pre_sum):
        left, right = 0, arr[-1]
        while left < right:
            mid = left + (right - left) // 2
            if self.calc_sum(arr, mid, pre_sum) < target:
                left = mid + 1
            else:
                right = mid
        return left

    def findBestValue(self, arr: List[int], target: int) -> int:
        size = len(arr)
        arr.sort()
        pre_sum = [0 for _ in range(size + 1)]

        for i in range(size):
            pre_sum[i + 1] = pre_sum[i] + arr[i]

        value = self.binarySearchValue(arr, target, pre_sum)

        sum_1 = self.calc_sum(arr, value, pre_sum)
        sum_2 = self.calc_sum(arr, value - 1, pre_sum)
        diff_1 = abs(sum_1 - target)
        diff_2 = abs(sum_2 - target)

        return value if diff_1 < diff_2 else value - 1
本站总访问量  次  |  您是本站第  位访问者