本文共 2543 字，大约阅读时间需要 8 分钟。

上一篇博客讲解了找出无序数组中位数的方法，找无序数组第K大数的方法跟中位数的方法差不多，K值可以类比成中位数的值，所以方法还是差不多的，分别是1.排序+取值 2.快排思想 3.桶排序。上一篇博客详细讲了这三种方法。在这里附上上一篇博客的链接：

这里我们以Leetcode中215题为例进行讲解

1 排序+取值

这个方法就不多说了。

2 快排思想

这里主要说一下快排哨兵元素选取的问题。

一般快排选哨兵元素都是选区间第一个为哨兵，然后左右指针移动，因为这样写起来比较简单，但是经过我实验发现，选首元素为哨兵运行速度会非常慢！！！ 这里附上我选首元素为哨兵元素的代码：

class Solution {
       public int findKthLargest(int[] nums, int k) {
           int left=0,right=nums.length-1;        int loc=quicksort(nums,left,right);        int tarloc=nums.length-k;        while(true)        {
               if(loc==tarloc) break;            else if(loc>tarloc) loc=quicksort(nums,left,loc-1);            else loc=quicksort(nums,loc+1,right);        }        return nums[loc];    }    public int quicksort(int[] nums,int left,int right)    {
           int target=nums[left];        while(left
   
    =target) right--;            nums[left]=nums[right];            while(left
    
     <=target) left++;            nums[right]=nums[left];        }        nums[left]=target;        return left;    }}
    
   

附上运行速度：

我靠，真的是慢的要死啊。 我在讨论区看有人说哨兵元素改成中间元素会快很多，然后我又改了很长时间(因为选中间元素的话意味着哨兵元素最后的位置会不确定，所以需要以左右指针的位置确定继续往哪个区间找),最后还是参考着九章算法的解析完成的，在这里附上链接： 代码如下：

class Solution {
       public int findKthLargest(int[] nums, int k) {
           return quicksort(nums,0,nums.length-1,nums.length-k);    }    public int quicksort(int[] nums,int left,int right,int k)    {
           if(left==right) return nums[left];        int target=nums[(left+right)/2];        int start=left,end=right;        while(start<=end)        {
               while(start<=end&&nums[start]
   
    target) end--;            if(start<=end)            {
                   int temp=nums[start];                nums[start]=nums[end];                nums[end]=temp;                start++; end--;            }        }        if(end>=k&&end>=left) return quicksort(nums,left,end,k);        else if(start<=k&&start<=right) return quicksort(nums,start,right,k);        return nums[k];    }}
   

这次运行速度真的是快的飞起！

3 利用最小堆

这里只需要用一个小顶堆即可，存k个较大的数，当有数插入后，把堆顶元素去除，然后继续循环操作。

代码如下：

class Solution {
       public int findKthLargest(int[] nums, int k) {
           Queue
   
     minHeap = new PriorityQueue
    
     ();        Queue
     
       maxHeap = new PriorityQueue
      
       (new Comparator
       
        (){
               public int compare(Integer o1,Integer o2){
                   return o2-o1;            }        });        for (int i=0;i
        
         =k) minHeap.poll(); } return minHeap.peek(); }}
        
       
      
     
    
   

不过时间方面不是很理想。

总结

以上就是三种找无序数组第K大数的方法，可以看出优化后的利用快排思想速度是最快的。

转载地址：http://ccaen.baihongyu.com/