查找第K大元素

2019-11-10 23:05:09

字體：大中小

供稿：網(wǎng)友

查找第k大元素

問題描述

給定一個(gè)無需數(shù)組a,長(zhǎng)度為n,以及一個(gè)整數(shù)k（0

問題分析

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

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

算法描述

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

代碼

//查找第k大的元素為了簡(jiǎn)便起見 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); } }

上一篇：PAT甲級(jí)1040

下一篇：PAT-B 1016. 部分A+B (15)