題目描述

有一個整數數組，請你根據快速排序的思路，找出數組中第K大的數。

給定一個整數數組a,同時給定它的大小n和要找的K(K在1到n之間)，請返回第K大的數，保證答案存在。

?

擴展思考：如何處理數組中的重復元素？比如，對于數組a={1,3,5,2,2}，第四大的元素應該是2還是1呢？

本文作這種分類：

如果第四大的元素是2，說明在處理第k大的元素時不處理重復的數據，也就是將原數組進行降序排序后，下標為k-1的元素。這種處理方法稱之為“不處理重復數據方法”；

如果第四大的元素是1，說明已經忽略重復的數據了，這時候需要首先對a進行去重處理（可以用哈希表），然后再進行討論。這種處理方法稱之為“去除重復數據方法”。

?

下面的方法都默認為第一種。

?

分治法

快速排序使用了分治法的策略。它的基本思想是，選擇一個基準數（一般稱之為樞紐元），通過一趟排序將要排序的數據分割成獨立的兩部分：在樞紐元左邊的所有元素都不比它大，右邊所有元素都比它大，此時樞紐元就處在它應該在的正確位置上了。

在本問題中，假設有N個數存儲在數組a中。我們從a中隨機找出一個元素作為樞紐元，把數組分為兩部分。其中左邊元素都不比樞紐元大，右邊元素都不比樞紐元小。此時樞紐元所在的位置記為mid。

如果右半邊（包括a[mid]）的長度恰好為k，說明a[mid]就是需要的第k大元素，直接返回a[mid]。

如果右半邊（包括a[mid]）的長度大于k，說明要尋找的第k大元素就在右半邊，往右半邊尋找。

如果右半邊（包括a[mid]）的長度小于k，說明要尋找的第k大元素就在左半邊，往左半邊尋找。

?

public class FindKth {public static void main(String[] args) {// [1,3,5,2,2],5,3int arr[] = {1,3,5,2,2};datastructure.FindKth f = new datastructure.FindKth();int result = f.findKth(arr, 5, 1);System.out.println(result);for(int t : arr){System.out.print(t+" ");}System.out.println("");}public int findKth(int[] a, int n, int k) {return find(a, 0,n-1, k);}public int find(int[] a, int start, int end, int k){// 比第一個元素大的放左邊，小的放右邊int p = partition(a, start, end);if(p+1 < k){return find(a, p+1,end, k);}if(p+1 > k){return find(a, start, p-1, k);}return a[p];}public int partition(int[] a, int start, int end){int i = start;int j = end + 1;int V = a[start];while(true){while(a[++i] > V){ // 直到比V小if(i>=end) break;}while(a[--j] < V){// 直到比V大if(j<=start) break;}if(i >= j)break;// 交換i，j位置的值exchange(a,i,j);}exchange(a,start,j);return j;}private void exchange(int[] a, int i, int j) {int temp = a[i];a[i] = a[j];a[j] = temp;} }

?

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:查找第K大元素算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。