SHARE
TWEET

Untitled

bbescos Feb 23rd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.     // Run-time complexity O(max(n, klogn))
  4.     // Memory complexity O(n)
  5.     /*
  6.     int findKthLargest(vector<int>& nums, int k) {
  7.        
  8.         // O(n)
  9.         priority_queue<int> pq_nums(nums.begin(), nums.end());
  10.        
  11.         // O(klogn)
  12.         for (int i = 0; i < k - 1; ++i)
  13.             pq_nums.pop();
  14.        
  15.         return pq_nums.top();
  16.     }
  17.     */
  18.    
  19.     // Run-time complexity O(max(k, (n-k)logk))
  20.     // Memory complexity O(k)
  21.     int findKthLargest(vector<int>& nums, int k) {
  22.        
  23.         // O(k)
  24.         priority_queue<int, vector<int>, greater<int>> pq_nums(nums.begin(), nums.begin() + k);
  25.        
  26.         // O((n-k)logk)
  27.         for (int i = k; i < nums.size(); ++i) {
  28.             if (nums[i] > pq_nums.top()) {
  29.                 pq_nums.pop();
  30.                 pq_nums.push(nums[i]);
  31.             }
  32.         }
  33.        
  34.         return pq_nums.top();
  35.     }
  36.    
  37. };
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top