Given an integer array arr
and a target value target
, return the integer value
such that when we change all the integers larger than value
in the given array to be equal to value
, the sum of the array gets as close as possible (in absolute difference) to target
.
In case of a tie, return the minimum such integer.
Notice that the answer is not neccesarilly a number from arr
.
Example 1:
Input: arr = [4,9,3], target = 10 Output: 3 Explanation: When using 3 arr converts to [3, 3, 3] which sums 9 and that's the optimal answer.
Example 2:
Input: arr = [2,3,5], target = 10 Output: 5
Example 3:
Input: arr = [60864,25176,27249,21296,20204], target = 56803 Output: 11361
Constraints:
1 <= arr.length <= 104
1 <= arr[i], target <= 105
Solution: Binary Search
Find the smallest number x s.t. sum of the mutated array is >= target. Answer must be either x or x – 1.
Note, the search range should be [0, max(arr))
Time complexity: O(nlogm)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua] class Solution { public: int findBestValue(vector<int>& arr, int target) { int l = 0; int r = *max_element(begin(arr), end(arr)); int ans = 0; auto sum = [&](int v) { int ans = 0; for (int x : arr) ans += min(x, v); return ans; }; while (l < r) { int m = l + (r - l) / 2; if (sum(m) >= target) r = m; else l = m + 1; } return abs(sum(l) - target) < abs(sum(l - 1) - target) ? l : l - 1; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment