C++ solutions: O(nlgk) by Min-Heap and O(n) by partition


  • 9
    T

    Solution 1: O(nlgk) by using min-heap

    class Solution {
    public:
        int findKthLargest(vector<int>& nums, int k) 
    	{
    		size_t len = nums.size();
    		if(len < k) return 0;
    
    		priority_queue<int, std::vector<int>, std::greater<int>> q;
    		for(auto &v : nums)
    		{
    			if(q.size() < k)
    			{
    				q.push(v);
    			}
    			else if (v > q.top())
    			{
    				q.pop();
    				q.push(v);
    			}
    		}
            return q.top();
        }
    };
    

    Solution 2: O(n) by partitioning recursively

    class Solution {
    public:
    	int partition(vector<int>& nums, int i, int j)
    	{
    		if (i == j) return i;
    
    		int pivot = nums[i];
    		std::swap(nums[i], nums[j]);
    		
    		int i0 = i;
    		for(int k = i; k < j; k ++)
    		{
    			if(nums[k] <= pivot)
    			{
    				std::swap(nums[k], nums[i0 ++]);
    			}
    		}
    		std::swap(nums[i0], nums[j]);
    		return i0;
    	}
        int findKthLargest(vector<int>& nums, int k) 
    	{
    		size_t len = nums.size();
    		int pi = 0;
    		int tgt = len - k;
    
    		int a = 0, b = len - 1;
    		while((pi = partition(nums, a, b)) != tgt)
    		{
    			if(pi < tgt)
    			{
    				a = pi + 1;
    			}
    			else if(pi > tgt)
    			{
    				b = pi - 1;
    			}
    		}
    		return nums[pi];
        }
    };

  • 2
    K

    Thanks for sharing, your first solution could be simplified as:

    int findKthLargest(vector<int>& nums, int k) {
         std::priority_queue<int, std::vector<int>, std::greater<int>> q;
         for (auto &v : nums) {
               q.push(v);
               if (q.size() > k) {
                     q.pop();
               }
        }
        return q.top();
    }
    

  • 0
    L

    Thanks.
    Really smart method!


  • 0
    Y

    @lanshan317
    Actually it's not the same. We should avoid adding the value to the heap if it's smaller than the top and size == k.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.