序言
今天分享的這道題,也是在分治策略上非常經(jīng)典的題目. 而且這個題目多次出現(xiàn)在互聯(lián)網(wǎng)頭部企業(yè)作為面試的算法題. 比如字節(jié),騰訊.這道題目,實際上有多種解決方案. 今天分享的是其中一個解決方案. 后續(xù)也會更新它的其他解法.
在求解樞軸上,為了讓讀者更加快速的理解它的求解過程和變換. 特地畫了圖.以及在文章末尾貼上的完整代碼.以及代碼中加上了比較詳細的注釋. 給大家輔助理解. 希望能加速你的對這道的理解與實現(xiàn)~
嗯. 我要開始寫了~~~
1.1 最小K個數(shù)
**難度系數(shù): ☆☆☆☆
題目來源: LeetCode 下分治策略專題
題目描述: 設(shè)計一個算法, 找出數(shù)組中最小的k個數(shù). 以任意順序返回這k個數(shù)均可;
輸入:arr = [1,3,5,7,2,4,6,8] , k = 4;
輸出: [1,2,3,4]
提示:
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))
題目解讀:
這個問題就是想要你從10w 個數(shù)字找出 最小的k 個數(shù);
關(guān)鍵詞: 數(shù)量級10w, 最小的k個數(shù) , 返回順序任意;
出現(xiàn)過企業(yè)面試題: 字節(jié)跳動,騰訊
1.2 快排實現(xiàn)最小K個數(shù)
LeetCode 執(zhí)行結(jié)果
問題分析:
其實這個問題就是一個非常經(jīng)典的快排問題. 但是大多數(shù)人遇到這個問題時 總是被 前面的數(shù)量級 總認為這樣的問題無法通過排序算法完成. 問題的表現(xiàn)形式,常常用以下方式描述: "如何從10萬個數(shù)中找到最大的100個數(shù)". 實際上這個問題就是今天我們要探討的 算法題. ** 設(shè)計一個算法, 找出數(shù)組中最小的k個數(shù). 以任意順序返回這k個數(shù)均可; **
這個問題在LeetCode 上"分治策略"題庫標(biāo)簽下, 實際上使用快速排序就是一種非常典型且明顯的分治策略了. 快速排序(Quick Sort)的基本思想: 通過一趟排序?qū)⒋判蛴涗浄指畛瑟毩⒌膬刹糠? 其中一部分記錄的關(guān)鍵字均為另一部分記錄的關(guān)鍵字小. 則可分別對兩部分記錄繼續(xù)進行排序, 以達到整個排序有序的目的;
值得注意的地方是, 使用快速排序后會讓源數(shù)據(jù)的數(shù)據(jù)位置發(fā)生變化. 但是在這樣的改變題目中明確指出是可以被允許的. 這個細節(jié)也是面試官會和你討論的一個小細節(jié);
1.3 快速排序思想
快速排序其實就是冒泡排序的升級, 它們都屬于交換排序;
快速排序也是通過不斷的比較和移動交換來實現(xiàn)排序的.只不過它的實現(xiàn),增大了記錄的比較和移動的距離; 將關(guān)鍵字較大的記錄從前面直接移動到后面; 關(guān)鍵字較小的記錄從后面直接移動到前面,從而減少了總的比較次數(shù)和移動交換次數(shù);
從快速排序的思想字母以上看, 好像這樣的計算是非常復(fù)雜且繁瑣的. 但是并非如此. 接下來我們就跟著 我的文字, 來快速理解, 快速排序的思路.
設(shè)計一個smallestK 函數(shù)思路:
- 判斷當(dāng)前的數(shù)組是否為空/數(shù)組長度是否小于0,以及查找的k數(shù)是否小于0,返回的size是否賦予了對應(yīng)的地址空間;
- low = 0, hight = arrSize -1;
- 求得樞軸,并且將數(shù)組樞軸左邊的關(guān)鍵字都比它小, 右邊的關(guān)鍵字都比樞軸對應(yīng)的關(guān)鍵字大;
- 將數(shù)組一分為二,對低子表進行排序,對高子表進行排序;
- 排序結(jié)束后,將數(shù)組arr 中前k個數(shù)據(jù)存儲到 ans 數(shù)組中并返回;
那么我們來看看 ****smallestK 的代碼實現(xiàn):
void QSort(int *arr, int low, int hight){
int pivot ;
if (low < hight) {
//將L->r[low,high]一分為二,算出中樞軸值 pivot;
pivot = Partition2(arr, low, hight);
printf("arr[%d] = %d\n",pivot,arr[pivot]);
//對低子表遞歸排序;
QSort(arr, low, pivot-1);
//對高子表遞歸排序
QSort(arr, pivot+1, hight);
}
}
int* smallestK2(int* arr, int arrSize, int k, int* returnSize){
//1.判斷數(shù)組是否為空,且arrsize 小于0則不符合排序的前提;
//1.判斷尋找最小的K數(shù),且returnSize 空間是否開辟成功,不符合則返回Null
if(arr == NULL || arrSize <= 0 || k <= 0 || returnSize == NULL){
if(returnSize != NULL) *returnSize = 0;
return NULL;
}
//進行快速排序QSort
QSort(arr, 0, arrSize);
//4. 創(chuàng)建一個數(shù)組reslut, 數(shù)組長度為k;
int* reslutArr = malloc(sizeof(int) * k);
*returnSize = k;
//循環(huán)將排序后的arr數(shù)組中的前k個元素存儲到數(shù)組reslutArr 中;
for(int i = 0; i < k; i++){
reslutArr[i] = arr[i];
}
return reslutArr;
}
-
QSort (L,1,L->length)中的1和L->Length代碼的意思,其實就是對當(dāng)前待排序的最小下標(biāo)值low和最大下標(biāo)值high. - 這段代碼的核心就是求解樞軸;
pivot = Partition(L,low,high). 在執(zhí)行之前,L.r數(shù)組值為{50,10,90,30,70,40,80,60,20}. -
Partition函數(shù)要做的,就先選取當(dāng)中一個關(guān)鍵字.比如選擇第一個關(guān)鍵字50. 然把它放在一個位置上,使得它左邊的值都比它小, 右邊的值都比它大. 我將這樣的關(guān)鍵字稱為樞軸(pivot); - 經(jīng)過
Partition(L,1,9)之后,數(shù)組變成了{20,10,40,30,50,70,80,60,90}; 并返回了5給pivot. 數(shù)字5表示50放置在數(shù)組下標(biāo)為5的位置. - 此時把原來位于50左右的2個數(shù)組
{20,10,40,30}和{70,80,60,90}. - 后面的遞歸就是調(diào)用 Q
Sort(L,1,5-1),QSort(L,5+1,9). 其實就是對{20,10,40,30}和{70,80,60,90}. 分別同樣進行Partition操作,直到順序全部正確為止;
注意,在 QSort 函數(shù)中,最關(guān)鍵的是Partition2 函數(shù) . 這個函數(shù)的作用是:
Partition2函數(shù)的功能
- 選取當(dāng)中一個關(guān)鍵字作為樞軸;
- 將它放在一個合適的位置上, 使得它的左邊的值都比它小, 右邊的值都比它大;
1.4 Partition 函數(shù)的實現(xiàn)與分析
既然我們明確了 Partition 的作用. 就先選取當(dāng)中一個關(guān)鍵字.比如選擇第一個關(guān)鍵字50. 然把它放在一個位置上,使得它左邊的值都比它小, 右邊的值都比它大. 我將這樣的關(guān)鍵字稱為樞軸(pivot);
那么接下來,我們要解決的問題是:
- 那么如何尋找樞軸變量?
- 如果將樞軸變量放在合適的位置,并且使得左側(cè)關(guān)鍵字均比它小,且右側(cè)的均比它大;
- 我們選擇子表中第1個記錄作為樞軸變量,
pivotkey = 50; - 從表的兩端往中間掃描; 開始第1層循環(huán)! 循環(huán)判斷依據(jù)是
low<high -
用高位
high與pivotkey進行比較找到比樞軸小的記錄. 交換到低端位置上; - 比較數(shù)組
L->r[high]與pivotkey進行比較. 如果low<hight并且L->r[high] >= pivotkey就遞減high;
- 判斷依據(jù):
L->r[high] >= pivotkey && low < high循環(huán)則繼續(xù)往下查找.high遞減; -
此時, 如圖. 當(dāng)
high = 9, low = 1; L->r[9] = 20; L->r[1] = 50; 所以不滿足循環(huán)條件,退出循環(huán), 那么此時需要交換Swap(L,1,9); 使得比pivotkey 小的數(shù)據(jù),交換到低端位置上;
- 接下來, 用低位
low與pivotkey進行比較找到比樞軸大的記錄. 交換到高端位置上; - 判斷依據(jù):
L->r[low] >= pivotkey && low < high循環(huán)則繼續(xù)往下查找.low++; - 此時,
L->r[1] = 20, pivotkey = 50; L->r[low] < pivotkey; 則low++; low = 2;
- 此時
L->r[2] = 10, pivotkey = 50; L->r[low] < pivotkey; 則low++; low = 3; - 此時
L->r[3] = 90, pivotkey = 50; L->r[low] > pivotkey; 則循環(huán)退出. - 交換
L->r[low] 與 L->r[high]的值; swap(L ,3,9);
- 第1次 往中間掃描結(jié)束!
- 但是此時
low < high . low = 3,high = 9. 還可以繼續(xù)進行第2次 往中間兩端交替向中間掃描;
Partition 函數(shù)的思路:
選取第一個關(guān)鍵字作為樞軸;
只要(low < high) 就循環(huán)持續(xù)的將表的兩端進行交替向中間掃描 (****<u>兩端交替循環(huán)</u>)
while 遍歷從[low,high]的高端位置開始找,找到比樞軸小的關(guān)鍵字(<u>高位調(diào)整循環(huán)</u>)
如沒有找到,則修改范圍. 將high 遞減;
如果找到進行交換到低端位置 swap(L,low,high);
while 遍歷從[low,high]的低端位置開始找,找到比樞軸大的關(guān)鍵字(<u>低位調(diào)整循環(huán)</u>)
如果沒有找到,則修改范圍,將low 遞增;
如果找到進行交換到高端位置 swap(L,low,high);
Partition 代碼實現(xiàn):
//③交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置
//此時在它之前(后)的記錄均不大(小)于它
int Partition(SqList *L,int low,int high){
int pivokey;
//pivokey 保存子表中第1個記錄作為樞軸記錄;
pivokey = L->r[low];
//① 從表的兩端交替地向中間掃描;
while (low < high) {
//② 比較,從高位開始,找到比pivokey更小的值的下標(biāo)位置;
while (low < high && L->r[high] >= pivokey)
high--;
//③ 將比樞軸值小的記錄交換到低端;
swap(L, low, high);
//④ 比較,從低位開始,找到比pivokey更大的值的下標(biāo)位置;
while (low < high && L->r[low] <= pivokey)
low++;
//⑤ 將比樞軸值大的記錄交換到高端;
swap(L, low, high);
}
//返回樞軸pivokey 所在位置;
return low;
}
最小K個數(shù)[快速排序?qū)崿F(xiàn)策略]完整代碼實現(xiàn)
int Partition2(int *L,int low,int high){
int pivotkey;
pivotkey = L[low];
while (low < high) {
while (low < high && L[high] >= pivotkey) high--;
swap(L+low, L+high);
while (low < high && L[low] <= pivotkey) low++;
swap(L+low, L+high);
}
return low;;
}
void QSort(int *arr, int low, int hight){
int pivot ;
if (low < hight) {
pivot = Partition2(arr, low, hight);
printf("arr[%d] = %d\n",pivot,arr[pivot]);
QSort(arr, low, pivot-1);
QSort(arr, pivot+1, hight);
}
}
int* smallestK2(int* arr, int arrSize, int k, int* returnSize){
//1.判斷數(shù)組是否為空,且arrsize 小于0則不符合排序的前提;
//1.判斷尋找最小的K數(shù),且returnSize 空間是否開辟成功,不符合則返回Null
if(arr == NULL || arrSize <= 0 || k <= 0 || returnSize == NULL){
if(returnSize != NULL) *returnSize = 0;
return NULL;
}
QSort(arr, 0, arrSize);
//4. 創(chuàng)建一個數(shù)組reslut, 數(shù)組長度為k;
int* reslutArr = malloc(sizeof(int) * k);
*returnSize = k;
//循環(huán)將排序后的arr數(shù)組中的前k個元素存儲到數(shù)組reslutArr 中;
for(int i = 0; i < k; i++){
reslutArr[i] = arr[i];
}
return reslutArr;
}
#define N 9
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, World!\n");
int d[10]={1,3,5,7,2,4,6,8,9};
int resultSize;
int *result = smallestK2(d, 8, 4, &resultSize);
for (int i = 0; i < resultSize; i++) {
printf("%d \n",result[i]);
}
return 0;
}
若有收獲，就點個贊吧
