How to solve the problem of array sum which is closest to the target value after transforming the array by LeetCode
This article will explain in detail how LeetCode solves the arrays and problems that are closest to the target value after transforming the array. The editor thinks it is very practical, so I share it for you as a reference. I hope you can get something after reading this article.
one
Topic description
Given an integer array arr and a target value target, return an integer value, so that all the values in the array that are greater than value become value, the sum of the array is closest to target (the smallest absolute value indicating the difference between the two) if there are multiple schemes that make it closest to target, please return the minimum value among these integers. For example, input arr=, target= 10, output 3, input arr= [60864, 25176, 27249, target=56803, output 11361.
two
Answer to the question
Train of thought: prefix and monotonicity this topic should first have an in-depth understanding of the topic. For arr [I], array and S=sum (arr [0: I] + arr [I] * (len (arr)-I)), so when sorting arr, it is found that S is a monotone function about arr.
So when S > = target appears, it means that the target value is between (ARR [I-1], arr [I]]. That is to say, there is a number x between (arr [I-1], arr [I]] such that sum (arr [0: I] + x * (len (arr)-I)) = target. At this time, the x obtained may be a decimal, because the minimum integer that satisfies the condition is required, so you can judge whether to round up or down according to the specific value of the decimal (similar to rounding, but rounding down when the decimal part is 0.5. It can be understood by looking for examples and calculating them in detail. If S is always less than target, the maximum value in arr is returned as required by the topic. Class Solution: def findBestValue (self, arr: List [int], target: int)-> int: arr.sort () pre = 0 for i in range (0 Len (arr)): if pre+arr [I] * (len (arr)-I) > = target: X = (target-pre) / (len (arr)-I) if x% 1 > 0.5: return ceil (x) else: return floor (x) pre+ = arr [I] return arr [- 1] about how LeetCode solves the transition number The array and problem closest to the target value after the group is shared here. Hope that the above content can be helpful to you, so that you can learn more knowledge, if you think the article is good, please share it for more people to see.
