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_1
、diff_2
。 - 输出差值小的那个值。
代码 #
|
|