这道题有三种解法，我都看了一下。
第一种利用java的sort方法实现，排好序以后，根据下标就可以取出第K个最大元素了，注意下标是len-K。java里面排序是这样写的——Arrays.sort(nums);
代码：
https://github.com/hanleirx/LeetCode/blob/master/215.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E7%AC%ACK%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%85%83%E7%B4%A0-sort
第二种方法是利用最小堆实现，java里面的最小堆是利用PriorityQueue实现，PriorityQueue有一些常用的方法，add是加入元素，poll是删除第一个元素，peek是查询第一个元素。
因为利用最小堆，所以我们可以保持PriorityQueue的元素数量为K，这样当我们加入一个元素的时候，最小的就会放在根节点，所以当我们发现队列中元素大于K时，删除的就是最小的了，这样当我们遍历数组之后，队列中剩下的就是K个元素，而且第K大的就在根节点，取出来就是所求。
代码：
https://github.com/hanleirx/LeetCode/blob/master/215.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E7%AC%ACK%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%85%83%E7%B4%A0-%E5%A0%86
第三种方法是利用快排，但因为需要第K大的元素，所以在快排的基础上面改动一点，我们只需要找到位置在下标是len-K的元素就行了，没有必要利用快排把整个数组排好。
记录一下快排的思想吧，因为我发现我一点都不熟了。思想大概是这样的：
题中说一定存在，所以呢我们可以通过快排后返回的位置和target进行比较，如果相等循环结束，返回这个值；位置大于target，说明target在左面，将位置减一作为右边界继续循环，否则加一作为左边界。
快排里面具体是这样实现的：
1 首先判断左右是否相等，相等返回任何一个；
2 其次，为了防止有序带来的极端情况，所以参考值我们不取第一个或者最后一个，利用随机数的方法，int ran = l + (int)(Math.random()*(r-l+1));这个可以生成[l,r]中的任何一个数字。
3 然后我们将随机生成的数字交换到最右侧。
4 现在我们可以开始利用参考值排序了，主要是讲大于和小于的分开。用两个指针分别指向最左面和右面的前一个元素，因为参考值已经在最右面了，当左面小于右面的时候，首先从做开始，遍历数组，小于等于参考值则左面指针一直加1，直到大于或者左面等于右面，结束循环；然后从右指针开始做相似的事情，只不过变成大于参考值，则右指针减1，两次循环都结束的时候，判断左右指针是否相等，不相等则交换数据。再不断进行外侧的循环，知道循环结束。
循环结束之后，我们需要将参考追放到正确的位置，判断如果左指针指向的位置的值大于参考值，则交换他们的位置，这样参考值就被放在了他该有的位置，返回这个位置，否则返回参考值所在的位置。
代码：
https://github.com/hanleirx/LeetCode/blob/master/215.%20%E6%95%B0%E7%BB%84%E4%B8%AD%E7%9A%84%E7%AC%ACK%E4%B8%AA%E6%9C%80%E5%A4%A7%E5%85%83%E7%B4%A0%E2%80%94%E2%80%94%E5%BF%AB%E6%8E%92
网友评论