LeetCode 1300. The array closest to the target value after transforming the array and | Python
Posted Jun 15, 2020 • 3 min read
1300. The array and the closest to the target value after changing the array
Source:LeetCode [ https://leetcode-cn.com/problems/sum-of-mutated-array-closest-to-target] ( https://leetcode-cn.com/problems/sum- of-mutated-array-closest-to-target)
Give you an integer array arr and a target value, please return an integer value, so that after all values in the array greater than value become value, the sum of the array is closest to the target(the closest is the absolute value of the difference between the two) Minimum).
If there are multiple schemes that are closest to the target, please return the minimum of these integers.
Note that the answer is not necessarily the number in arr.
Input:arr = [4,9,3], target = 10 Output:3 Explanation:When the value is selected as 3, the array will become [3, 3, 3], and the sum is 9, which is the closest plan to the target.
Input:arr = [2,3,5], target = 10 Output:5
Input:arr = [60864,25176,27249,21296,20204], target = 56803 Output:11361
- 1 <= arr.length <= 10^4
- 1 <= arr[i], target <= 10^5
Problem solving ideas
In this question, what may be more difficult is the question [value is an integer, array and close to target]and [the answer is not necessarily the number in arr]. In other words, the subject is the closest we want.
So the question now can be changed to consider how to judge proximity? The closest possible situation is listed below:
- Select a value and after the conversion, the sum of the array is equal to the target.(Of course, this is the ideal situation)
- The selected value is too large, the closeness becomes smaller;
- The selected value is too small, the closeness becomes larger.
- The second and third cases, the reverse may also be true.
How to consider the second and third cases, the solution adopted in this article is to determine the upper and lower boundaries, and compare the possible value values.
- First determine a value, transform the array, and sum
- If the converted array sum is the first one greater than or equal to target, then determine the upper and lower boundaries
- Because value is an integer, the final answer may fall on value, or it may be value-1
The specific code implementation is as follows.
class Solution: def findBestValue(self, arr:List[int], target:int) -> int: def cacl_change_sum(arr, value): res = 0 # Values greater than value are to be converted for num in arr: res += min(num, value) return res left = 0 right = max(arr) while left <right: mid =(left+ right) //2 # Calculate the sum of the converted array res = cacl_change_sum(arr, mid) # Find the first value such that the transformed array is greater than or equal to target if res <target: left = mid + 1 else: right = mid # When the first value is found such that the converted array sum is greater than or equal to target, the answer may fall in value or value-1 # Now, compare the results between the two, the smaller the closeness, the return is the result res1 = cacl_change_sum(arr, left) res2 = cacl_change_sum(arr, left-1) if res1-target <target-res2: return left return left-1
to sum up
First clarify the meaning of the question, because there are requirements for [value is an integer, array and close to target]and [the answer is not necessarily a number in arr], so the question can start from considering how to find the closest solution;
The binary search used in this article, specific methods:
- Determine a value first, transform and sum the array
- If the sum of the array at this time is the first value greater than or equal to the target value, then the upper and lower boundaries can be determined at this time
- Since value must be an integer, the answer may fall on value or value-1.
The article is original, if you feel it is well written, welcome to follow and like it. The WeChat public account "Book Collection" is updated at the same time, and attention and likes are also welcome.