之前去面試遇到了這個問題,題目:找出無序數組中第二大的數字。
定睛一看,好簡單,一次遍歷就可以找出第二大的數字,不過,這樣寫沒有什么特別之處,因為實在是太簡單了。自己仔細想想起了之前做過的題,看看有沒有什么類似的。于是,想起了之前在網上看到的一道面試題:找出無序數組中最小的k個數。 要找出最小的k個數,可以用快速選擇算法,只要在快速排序之后,樞紐剛好是第k+1個數,那么,他左邊的數,剛好就是最小的k個數。要找出無序數組中第二大的數字,可以這樣轉換:
0)假設數組中有n個元素,a1~an,而我們要求第k大的數字,就相當于求排序后的第m = n - k + 1個數字。
1)假設一次快速排序之后,如果樞紐的是第x個(1~n)。
2)如果x = m,則這個樞紐ax就是我們要求的第k大的數字,結束;如果x < m,則對a0 ~ ax-1進行一次快速排序,重復第2)步;如果x > m,則對ax+1 ~ an 進行一次快速排序,重復第2)步。
快速選擇的代碼如下:
~~~
//a[] - 要排序的數組
//b - 要排序的子區間的開始索引
//e - 要排序的子區間的結束索引
//k - 求出排序后第k個數
int quickselect(int a[], int b, int e, int k){
int i = b ;
int j = e + 1;
int x = a[i];
while(true){
while(a[++i] < x && i < j);
while(a[--j] > x);
if(i >= j)
break;
else
swap(a[i], a[j]);
}
a[b] = a[j];
a[j] = x;
if(k - 1 == j)
return a[j];
else if(k - 1 > j)
return quickselect(a, j + 1, e, k);
else
return quickselect(a, b, j - 1, k);
}
~~~
總結:快速選擇可以用于這類面試題:
1)求出無序數組中第k大的數
2)求出無序數組中最大/小的k個數