Leetcode 2208. Minimum Operations to Halve Array Sum
You are given an array?nums?of positive integers. In one operation, you can choose?any?number from?nums?and reduce it to?exactly?half the number. (Note that you may choose this reduced number in future operations.)
Return?the?minimum?number of operations to reduce the sum of?nums?by?at least?half.
?
Example 1:
Input: nums = [5,19,8,1]
Output: 3
Explanation: The initial sum of nums is equal to 5 + 19 + 8 + 1 = 33.?
The following is one of the ways to reduce the sum by at least half:?
Pick the number 19 and reduce it to 9.5.
Pick the number 9.5 and reduce it to 4.75.
Pick the number 8 and reduce it to 4.?
The final array is [5, 4.75, 4, 1] with a total sum of 5 + 4.75 + 4 + 1 = 14.75.?
The sum of nums has been reduced by 33 - 14.75 = 18.25,?
which is at least half of the initial sum, 18.25 >= 33/2 = 16.5.?
Overall, 3 operations were used so we return 3.?
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
Example 2:
Input: nums = [3,8,20]
Output: 3
Explanation: The initial sum of nums is equal to 3 + 8 + 20 = 31.?
The following is one of the ways to reduce the sum by at least half:
Pick the number 20 and reduce it to 10.
Pick the number 10 and reduce it to 5.
Pick the number 3 and reduce it to 1.5.?
The final array is [1.5, 8, 5] with a total sum of 1.5 + 8 + 5 = 14.5.?
The sum of nums has been reduced by 31 - 14.5 = 16.5,?
which is at least half of the initial sum, 16.5 >= 31/2 = 15.5.?
Overall, 3 operations were used so we return 3.?
It can be shown that we cannot reduce the sum by at least half in less than 3 operations.
?
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 107
如果將目前的總和降為一半以上，肯定是將最大的元素降為1半是速度最快的，所以就要每次判斷哪個(gè)是最大的元素，每次都要最值元素，優(yōu)先考慮優(yōu)先隊(duì)列，使用reverse order 的規(guī)則。
然后while 循環(huán)即可。
要是難題也能這么快做出來(lái)就好了。。。。。。。。
Runtime:?244 ms, faster than?62.55%?of?Java?online submissions for?Minimum Operations to Halve Array Sum.
Memory Usage:?59.3 MB, less than?56.37%?of?Java?online submissions for?Minimum Operations to Halve Array Sum.
