2208. Minimum Operations to Halve Array Sum

發表於 | 分類於

problem

solution

option 1 - heap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int halveArray(vector<int>& nums) {
        priority_queue<double> pq;
        double total = 0;
        for(int n:nums){
            pq.push(n);
            total+=n;
        }
        int step = 0;
        double cur = total;
        while(cur > total/2.0){
            double p = pq.top(); pq.pop();
            p /= 2.0;
            cur -= p;
            pq.push(p);
            step++;
        }
        return step;   
    }
};

analysis

  • time complexity O(nlogn)
  • space complexity (n)