c++ solution using minimum Heap


  • 0
    A
    int findKthLargest(vector<int> &nums, int k) {
              if(nums.empty() || k<1 || k>nums.size())
                  return 0;
    
              vector<int> minHeap;
    
              int n = nums.size();
        
              for(int i = 0; i < k; ++i) {
                    minHeap.push_back(nums[i]); 
              }
              make_heap(minHeap.begin(), minHeap.end(), greater<int>());
              
              for(int i = k; i<n; ++i) {
                  if(minHeap[0] < nums[i]) {
                        pop_heap(minHeap.begin(), minHeap.end(), greater<int>());
                        minHeap.pop_back();
                        
                        minHeap.push_back(nums[i]);
                        push_heap(minHeap.begin(), minHeap.end(), greater<int>());
                  }
              }
    
              return minHeap[0];
          }
    

Log in to reply
 

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