Top k Largest Numbers II (Ladder)

Description

Implement a data structure, provide two interfaces:

add(number). Add a new number in the data structure.
topk(). Return the top k largest numbers in this data structure. k is given when we create the data structure.

Example

s = new Solution(3);
> create a new data structure.
s.add(3)
s.add(10)
s.topk()
> return [10, 3]
s.add(1000)
s.add(-99)
s.topk()
> return [1000, 10, 3]
s.add(4)
s.topk()
> return [1000, 10, 4]
s.add(100)
s.topk()
> return [1000, 100, 10]

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   class Solution {
   private:
    priority_queue<int, vector<int>, greater<int>> minheap;  
    int knum;
   public:
    Solution(int k) {
        // initialize your data structure here.
        knum = k;
    }
    void add(int num) {
        // Write your code here
        if (minheap.size() < knum) {
            minheap.push(num);
        } else {
            minheap.push(num);
            minheap.pop();
        }
        return;
    }
    vector<int> topk() {
        // Write your code here
        if (minheap.empty()) {
            return {};
        }
        vector<int> result;
        while (!minheap.empty()) {
            result.push_back(minheap.top());
            minheap.pop();
        }
        int n = result.size();
        for (int i = 0; i < n; ++i) {
            minheap.push(result[i]);
        }
        reverse(result.begin(), result.end());
        return result;
    }
   };
   

Similar problems

x

Tags

x