LeetCode 1300. The array closest to the target value after transforming the array and | Python

Posted Jun 15, 20203 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)

Title


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.

Example 1:

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.

Example 2:

Input:arr = [2,3,5], target = 10
Output:5

Example 3:

Input:arr = [60864,25176,27249,21296,20204], target = 56803
Output:11361

prompt:

  • 1 <= arr.length <= 10^4
  • 1 <= arr[i], target <= 10^5

Problem solving ideas


Thinking:binary search

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.

Specific practices:

  • 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.

Code


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

Results


Achievement Results

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.