查找第K大元素

2019-11-10 20:35:49

字體：大中小

來源：轉載

供稿：網友

查找第k大元素

問題描述

給定一個無需數組a,長度為n,以及一個整數k（0

問題分析

首先大家能夠想到的，就是把數組進行排序，然后找出下標為k的元素。如果是用快速排序，那么整個過程的時間復雜度是O(nlogn)，顯然不夠好。接著上面的分析，如果用快速排序，但是明顯我們這個題目不需要把整個數組都排序，只需要排一部分就可以了（在代碼中能夠體會到）。好，我們就在快排的基礎上改進一下。

不了解快速排序的話，可以看快速排序，快速搞定

算法描述

首先通過軸值（pivot）將數組分為兩半，這時候軸值左邊的都比軸值小，右邊的都大于等于軸值。設最終軸值的位置是p，那么軸值一定是數組中第p大元素（仔細讀上句話）。舉例：a = {4,3,2,1,5,6,7,8,9} 我們選取a[0](4)為軸值，那么將數組劃分后，得：a = {3,2,1,4,5,6,7,8,9}，這時候軸值4的位置是3，我們可以看到，第三大的數就是4。那么我們可以通過軸值的位置與k進行比較，如果k==p，那么a[p]就是第k大的數了。如果k> p，那么軸值一定在[p+1,n]的范圍，所以我們只需要對右邊進行遞歸就好。如果k< p，只需要對左邊進行遞歸。

代碼

//查找第k大的元素為了簡便起見 k從0開始 public static int findKth(int[] a,int first,int last,int k){ if(first == last){ return a[first]; } int pivot = a[first];//軸值 int left = first , right = last; while(left!=right){ while(a[right]>=pivot && right!=left){ right--; } a[left] = a[right]; while (a[left]<pivot && right!=left){ left++; } a[right] = a[left]; } a[left] = pivot;//軸值的位置 if(left == k){ return pivot; } if(left>k){ return findKth(a,0,left-1,k); }else { return findKth(a,right+1,a.length-1,k); } }

上一篇：【LeetCode】496. Next Greater Element I

下一篇：myEclipse2014集成MyBatis插件自動生成代碼