:-: 12.1 数组中的第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 ≤ 数组的长度。 ``` **题目分析：** 我们求得是数组中第k大的元素，题目不难。 **新手有可能遇到的解题思路陷阱：** 无 **解题思路分析以及代码实现：** 第一种思路：先排序后直接取出。 第一种思路代码： ``` public int findKthLargest(int[] nums, int k) { Arrays.sort(nums); return nums[nums.length - k]; } ``` **复杂度分析：** 不做分析。 第一种思路代码2：采用希尔排序。 ``` public static int findKthLargest(int[] nums, int k) { int gap = 1, i, j, len = nums.length; int temp; while (gap < len / 3) { gap = gap * 3 + 1; } for (; gap > 0; gap /= 3) { for (i = gap; i < len; i++) { temp = nums[i]; for (j = i - gap; j >= 0 && nums[j] > temp; j -= gap) { nums[j + gap] = nums[j]; } nums[j + gap] = temp; } } return nums[nums.length - k]; } ``` **复杂度分析：** 时间复杂度：最坏：O(nlog^2n)、最优：O(n)。 空间复杂度：O(1)。 第二种思路：利用堆的特性，说到堆，它是优先队列(priority queue），它又叫"堆"(heap), 但是可能优先队列这个名字更容易理解一些。Java中PriorityQueue通过二叉小顶堆实现，每次移除元素重新构建二叉小顶堆。下面的一些博客可帮助理解。 [Java中的PriorityQueue](https://www.cnblogs.com/CarpenterLee/p/5488070.html) [Heap -> PriorityQueue](http://www.cnblogs.com/vamei/archive/2013/03/20/2966612.html) [Priority Queue/Heap (优先队列/堆)小结](http://x-wei.github.io/heap-summary.html) 第二种思路代码： ``` public static int findKthLargest(int[] nums, int k) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); for (int num : nums) { priorityQueue.add(num); if (priorityQueue.size() > k) { priorityQueue.poll(); } } return priorityQueue.peek(); } ``` **复杂度分析：** 不做分析。 **若有理解错误的、写错的地方、更好的思路，方法，望各位读者评论或者发邮件指正或指点我，不胜感激。**