Top k Largest Numbers (Ladder)

Description

Given an integer array, find the top k largest numbers in it.

Example
Given [3,10,1000,-99,4,100] and k = 3.
Return [1000, 100, 10].

Link

Lintcode_ladder

Method

1. x
2. x

Example

1. 1

   struct comparator {
    bool operator()(int i, int j) {
        return i > j;
    }
   };
   class Solution {
   public:
    /*
     * @param nums an integer array
     * @param k an integer
     * @return the top k largest numbers in array
     */
    vector<int> topk(vector<int>& nums, int k) {
        // Write your code here
        if (k > nums.size()) {
            return {};
        }
        // find k largest
        priority_queue<int, vector<int>, comparator > heap_min;
        vector<int> result(k, 0);
        int n = nums.size();
        int i = 0;
        while (i < n) {
            heap_min.push(nums[i]);
            if (heap_min.size() > k) {
                heap_min.pop();
            }
            i++;
        }
        // get result
        i = k-1;
        while (!heap_min.empty()) {
            result[i] = heap_min.top();
            heap_min.pop();
            i--;
        }
        return result;
    }
   };
   

Similar problems

x

Tags

x