Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

Day 71 2021.03.21

2208. The minimum number of operations to halve the array sum

  • Leetcode: leetcode-cn.com/problems/mi…
  • Difficulty: Medium
  • Method: Priority queue

Topic describes

  • I give you an array of positive integersnums. In each operation, you can go fromnums Select any number and reduce it to exactly half. (Note that you can continue with the halved number later.)
  • Please return tonumsArray and reduce the minimum operand by at least half.

The sample

  • Example 1
Input: nums = [5,19,8,1] Output: 3 Description: The initial sum of NUMs is 5 + 19 + 8 + 1 = 33. Here's one way to reduce the array sum by at least half: Select the number 19 and reduce it to 9.5. Select the number 9.5 and reduce it to 4.75. Select the number 8 and reduce it to 4. The final array is [5, 4.75, 4, 1], and is 5 + 4.75 + 4 + 1 = 14.75. The sum of nums is reduced by 33 to 14.75 = 18.25, which is more than half of the original sum, 18.25 >= 33/2 = 16.5. We need 3 operations to do that, so return 3. You can prove that you cannot reduce the array sum by at least half with less than three operations.Copy the code
  • Example 2
Input: nums = [3,8,20] Output: 3 Description: The initial sum of NUMs is 3 + 8 + 20 = 31. Here's one way to reduce the array sum by at least half: Select the number 20 and reduce it to 10. Select the number 10 and reduce it to 5. Select the number 3 and reduce it to 1.5. The final array is [1.5, 8, 5], and 1.5 + 8 + 5 = 14.5. The sum of nums is reduced by 31-14.5 = 16.5, which is more than half of the original sum, 16.5 >= 31/2 = 16.5. We need 3 operations to do that, so return 3. You can prove that you cannot reduce the array sum by at least half with less than three operations.Copy the code

prompt

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 107

Thinking summary

  • Use of priority queuesPriorityQueue
  • Find the minimum operand to reduce the array sum by half.
  • So each time you need to find the largest value in the current array, you need to take it in half, so that you can reduce the array sum in half with the fewest operands

Specific steps

  • I’m going to sum up the original arraytotal, and half of the array sum is calledhalf
  • The number in the queue must be the largest number in the current array. Take the current maximum number, cut it in half, and put it in the priority queue.
  • So if we do that, we’re guaranteed to be less thanhalfMust be the smallest operand.

ACcode

  • jsIt’s not built inPriorityQueuePriority queue, butLeetcodeThere are built-in functionsMaxPriorityQueue
var halveArray = function(nums) {
    // Array summation function with initial value 0
    let total = nums.reduce((cur, next) = > cur + next, 0)
    const half = total / 2
    const queue = new MaxPriorityQueue()
    for (const num of nums) {
        queue.enqueue(num, num)
    }
    let ans = 0
    while (total > half) {
        let { element } = queue.dequeue()
        ans ++
        element /= 2
        total -= element
        queue.enqueue(element, element)
    }
    return ans
};
Copy the code

conclusion

  • Remember a few ways to use priority queues
    • new MaxPriorityQueue()Create a queue
    • queue.enqueue()The team
    • queue.dequeue()Out of the team