LeetCode 215. 數組中的第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 ≤ 數組的長度。

先來個暴力點的通用方法：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length-k];
    }
}
           

當然也可以采用PrioritQueue:

如果不明白優先隊列：

優先隊列中的元素可以按照任意順序插入，卻總是按照排序的順序進行檢索。也就是說，無論何時調用remove（）\poll（）方法，總會獲得但目前優先隊列中的最小元素。然而優先隊列并沒有對所有的元素進行排序。如果用疊代的範式處理這些元素，并不需要對他們進行排序。

優先隊列使用了一個優雅且高效的資料結構，稱為堆（heap）。堆是一個可以自我調整的二叉樹，對樹執行添加（add\offer）和删除（remove\poll）操作可以讓最小的元素移動到根，而不必花費時間對元素進行排序。

哎呀說了這麼多：反正priorityQueue這個資料結構 你無論remove、poll、删的是隊中的最小（優先級最小）元素，無論什麼時候peek的取的是隊列中的最小（優先級最小）元素，無論你怎麼加元素 add、offer 加後、這個隊列一直保持有序、

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Queue<Integer> q =new PriorityQueue<Integer>(k);
        for(int i =0;i<nums.length;i++){
            if(q.size()<k){      //将優先隊列（k）填滿
                q.offer(nums[i]);
            }else{
                if(nums[i]>q.peek()){  //peek總取出隊列中最小元素
                    q.poll();          //poll總删除隊列中最小元素；
                    q.offer(nums[i]);  //将這個元素加入隊列
                }
            }
        }
        return q.peek();
    }
}
           

當然也可以使用快速排序：

class Solution {
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int parrtion(int[] nums,int p,int r){
        int x = nums[r];
        int i = p-1;
        for(int j = p;j<r;j++){
            if(nums[j]<x){
                i++;
                swap(nums,i,j);
            }
        }//end of for
        swap(nums,r,i+1);
        return i+1;
    }
    
    public void quicksort(int[] nums,int p,int r){
        if(p<r){
            int q = parrtion(nums,p,r);
            quicksort(nums,p,q-1);
            quicksort(nums,q+1,r);
        }
    }
    public int findKthLargest(int[] nums, int k) {
        quicksort(nums,0,nums.length-1);
        return nums[nums.length-k];
    }
}
           

可看的出來将數組分割為兩部分的時候我們完全隻考慮存在倒數第k大數的數組部分，而另一部分就不用去管了

優化後的快排思想：

class Solution {
    public void swap(int[] nums,int i,int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public int parrtion(int[] nums,int p,int r){
        int x = nums[r];
        int i = p-1;
        for(int j = p;j<r;j++){
            if(nums[j]>x){     //按從大到小排  排序後nums[k-1] 即為所求
                i++;
                swap(nums,i,j);
            }
        }//end of for
        swap(nums,r,i+1);
        return i+1;
    }
    
    public int  quicksort(int[] nums,int p,int r,int k){
        if(p>=r) return nums[p];
        
        int q = parrtion(nums,p,r);
        if(q ==k-1) return nums[q];//如果找到k-1位置 傳回第k大的數
        else if(q>=k){    //如果q>=k說明第k大的數在數組左半部分
            return quicksort(nums,p,q-1,k);//隻在左邊找就可以了
        }else{
             return quicksort(nums,q+1,r,k);//在右邊找
            }
           
           
       
        
    }
    public int findKthLargest(int[] nums, int k) {
        return quicksort(nums,0,nums.length-1, k);
        
    }
}