数组中的第k个最大元素

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2

输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4

输出: 4

说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

 

1 class Solution { 2     public int findKthLargest(int[] nums, int k) { 3         int begin=0; 4         int end=nums.length-1; 5         k=nums.length+1-k; 6         while(begin
     
       high) {17             return 0;18         }19         key = nums[low]; // 用子表的第一个记录做基准20         while (low < high) { // 从表的两端交替向中间扫描21             while (low < high && nums[high] >= key)22                 high--;23             if (low < high)24                 swap(nums,low,high);// 用比基准小的记录替换低位记录25             while (low < high && nums[low] < key)26                 low++;27             if (low < high) // 用比基准大的记录替换高位记录28                 swap(nums,low,high);29         }30         return low;31     }32 33     private void swap(int[] a, int i, int j) {34         int t = a[i];35         a[i] = a[j];36         a[j] = t;37     }38 }