Leetcode 215: Kth Largest Element in an Array

时间：2017-12-02 10:17:08 收藏：0 阅读：221

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array‘s length.

 1 public class Solution {
 2     public int FindKthLargest(int[] nums, int k) {        
 3         return QuickSelect(nums, 0, nums.Length - 1, nums.Length - k);
 4     }
 5     
 6     private int QuickSelect(int[] nums, int start, int end, int k)
 7     {
 8         if (start >= end) return nums[start];
 9         
10         int i = start, j = start, pivot = nums[end];
11         
12         while (j < end)
13         {
14             if (nums[j] < pivot)
15             {
16                 if (i != j)
17                 {
18                     var tmp = nums[j];
19                     nums[j] = nums[i];
20                     nums[i] = tmp;
21                 }
22                 
23                 i++;
24             }
25             
26             j++;
27         }
28         
29         if (i != end)
30         {
31             nums[end] = nums[i];
32             nums[i] = pivot;
33         }
34         
35         if (k == i - start)
36         {
37             return nums[i];
38         }
39         else if (k > i - start)
40         {
41             return QuickSelect(nums, i + 1, end, k - i + start - 1);     
42         }
43         else
44         {
45             return QuickSelect(nums, start, i - 1, k);
46         }
47     }
48 }

原文：http://www.cnblogs.com/liangmou/p/7952222.html