[Algorithm] 5. Kth Largest Element-白红宇

Find K-th largest element in an array.

Example

In array [9,3,2,4,8], the 3rd largest element is 4.

In array [1,2,3,4,5], the 1st largest element is 5, 2nd largest element is 4, 3rd largest element is 3 and etc.

Notice

You can swap elements in the array

Answer

1     /** 2      * @param n: An integer 3      * @param nums: An array 4      * @return: the Kth largest element 5      */ 6     int kthLargestElement(int n, vector
          
            &nums) { 7         // find out the kth largest number in an array. 8         int temp=0; 9         for(int i=1; i<=n; i++)10         {11             for(int j=0; j
           
            = nums[j+1])15                 {16                     temp = nums[j];17                     nums[j] = nums[j+1];18                     nums[j+1] = temp;19                 }20             }21         }22         23         return nums[nums.size()-n];24     }

Better Solution

1     /** 2      * @param n: An integer 3      * @param nums: An array 4      * @return: the Kth largest element 5      */ 6       7     int quick_sort(vector
           
             &nums, int l, int r) 8     { 9         int key=nums[l];10         while(l
            
             = key) && (l

&nums) {23 // Using qsort method to find the kth largest number.24 if(n>nums.size() || n==0 || nums.size()==0) return -1;25 26 int left=0, right=nums.size()-1, k=nums.size()-n, pivot=0;27 28 while(true){29 pivot = quick_sort(nums, left, right);30 if(pivot==k){31 return nums[k];32 }else if(pivot

Best Solution

1     /** 2      * @param n: An integer 3      * @param nums: An array 4      * @return: the Kth largest element 5      */ 6     int kthLargestElement(int n, vector
           
             &nums) { 7         // Using priority queue to solve it. 8         if(n>nums.size() || n==0 || nums.size()==0)   return -1; 9         10         priority_queue

, greater

> pri_queue;11 for(int i=0; i

pri_queue.top() )18 {19 pri_queue.pop();20 pri_queue.push(nums[i]);21 }22 }23 24 return pri_queue.top();25 }

Tips

It is a good way to use STL container(priority queue) to solve the problem.