一、問題描述

給定一個(gè)數(shù)組，數(shù)組中的數(shù)據(jù)無序，在一個(gè)數(shù)組中找出其第k個(gè)最小的數(shù)，例如對(duì)于數(shù)組x，x = {3，2，1，4，5，6}，則其第2個(gè)最小的數(shù)為2。

二、解題思路

本算法跟快排的思想相似，首先在數(shù)組中選取一個(gè)數(shù)centre作為樞紐，將比centre小的數(shù)，放到centre的前面將比centre大的數(shù)，放到centre的后面。如果此時(shí)centre的位置剛好為k，則centre為第k個(gè)最小的數(shù)；如果此時(shí)centre的位置比k前，則第k個(gè)最小數(shù)一定在centre后面，遞歸地在其右邊尋找；如果此時(shí)centre的位置比k后，則第k個(gè)最小數(shù)一定在centre后面，遞歸地在其左邊尋找。

注意：centre的位置=其下標(biāo)值+1，因?yàn)閿?shù)組中的第一個(gè)元素的下標(biāo)為0。

從上面的描述中，我們可以看到這個(gè)算法運(yùn)用了減治的方法求解。減治的思想與分治非常相似，同樣是在一次操作中，削減問題的規(guī)模，只是分治把每個(gè)子問題求解后，要合并每個(gè)子問題的解才能得到問題，而減治的方法，卻不用合并子問題的解，子問題的解，直接就是原問題的解。舉個(gè)例子來說，就像快排和二分查找算法，前者是分治，后者是減治。因?yàn)榭炫乓鹊剿械淖訑?shù)組都排完序，原數(shù)組才有序，而二分查找卻不用，它每執(zhí)行一次查找，直接丟棄一半的數(shù)組，而不用合并子問題的解。不過也有不少書，把他們都?xì)w為分治法。

三、代碼實(shí)現(xiàn)

考慮到代碼的通用性，使用了模板函數(shù)，如果看不懂模板函數(shù)，則只需要忽略template<typename T>，并把T看作是一個(gè)類型即可。代碼如下：

[cpp]?view plaincopyprint?

//返回?cái)?shù)組中的第k個(gè)最小元素的啟動(dòng)函數(shù)，注意會(huì)破壞原數(shù)組??

template<typename?T>??

T?FindTheKMin(T?*x,?int?x_size,?int?k);??

//實(shí)現(xiàn)查找數(shù)組中第K個(gè)最小元的功能函數(shù)??

template<typename?T>??

T?TheKMin(T?*x,?int?left,?int?right,?int?k);??

template<typename?T>??

T?FindTheKMin(T?*x,?int?x_size,?int?k)??

{??

????//判斷k的值是否過大，即超過數(shù)組的大小??

????//若是則返回第0個(gè)元素，主要是為了防止無效的遞歸??

????if(x_size?<?k)??

????????return?x[0];??

????return?TheKMin(x,?0,?x_size-1,?k);??

}??

template<typename?T>??

T?TheKMin(T?*x,?int?left,?int?right,?int?k)??

{??

????//取數(shù)組最后一個(gè)元素為樞紐??

????T?centre?=?x[right];??

????int?i?=?left;??

????int?j?=?right?-?1;??

????while(true)??

????{??

????????//從前向后掃描，找到第一個(gè)小于樞紐的值，??

????????//在到達(dá)數(shù)組末尾前，必定結(jié)束循環(huán),因?yàn)樽詈笠粋€(gè)值為centre??

????????while(x[i]?<?centre)??

????????????++i;??

????????//從后向前掃描，此時(shí)要檢查下標(biāo)，防止數(shù)組越界??

????????while(j?>=?left?&&?x[j]?>?centre)??

????????????--j;??

????????//如果沒有完成一趟交換，則交換??

????????if(i?<?j)??

????????????Swap(x[i],?x[j]);??

????????else??

????????????break;??

????}??

????//把樞紐放在正確的位置??

????Swap(x[i],?x[right]);??

????//如果此時(shí)centre的位置剛好為k，則centre為第k個(gè)最小的數(shù)??

????if(i+1?==?k)??

????????return?x[i];??

????else?if(i+1?<?k)??

????{??

????????//如果此時(shí)centre的位置比k前,遞歸地在其右邊尋找??

????????TheKMin(x,?i+1,?right,?k);??

????}??

????else??

????{??

????????//如果此時(shí)centre的位置比k后,遞歸地在其左邊尋找??

????????TheKMin(x,?left,?i-1,?k);??

????}??

}??

代碼說明：

在上面的代碼中，我們要注意，TheKMin函數(shù)的最后的if-else，這個(gè)算法不同于快排，當(dāng)樞紐不是要找到元素時(shí)，它只會(huì)選擇其中一個(gè)方向的子數(shù)組繼續(xù)尋找，而不像快排那樣，會(huì)在兩個(gè)方向的子數(shù)組中繼續(xù)。從上面的代碼來看，其運(yùn)行速度應(yīng)該在使用相同選取樞紐的策略的快排之上，時(shí)間復(fù)雜度為O(N)。

同時(shí)，當(dāng)K值不合理時(shí)，我們只能返回第0個(gè)元素，這點(diǎn)有一點(diǎn)的不合理，但是，我不知道該返回一個(gè)什么樣的合適的值，因?yàn)樗欠盒偷摹?/span>

其實(shí)，這段代碼有兩個(gè)缺陷，第一個(gè)，就是在查找時(shí)，破壞了數(shù)組原來的數(shù)據(jù)（交換了位置）；第二個(gè)是，當(dāng)類型T的復(fù)制和構(gòu)造開銷較大時(shí)，直接多次交換兩個(gè)元素，可能會(huì)帶來相當(dāng)大。

另一種實(shí)現(xiàn)

下面，再來看看另一種實(shí)現(xiàn)，算法的思想和策略相同，但是使用了一個(gè)跟蹤數(shù)組track，用來跟蹤使用第一種方法下的數(shù)據(jù)的交換情況，利用跟蹤數(shù)組的元素交換代替原數(shù)組中元素的交換，解決了上面提到的兩個(gè)問題。它的實(shí)現(xiàn)如下：

[cpp]?view plaincopyprint?

//返回?cái)?shù)組中的第中個(gè)最小元素的下標(biāo)的啟動(dòng)函數(shù)，不破壞原數(shù)組??

template<typename?T>??

int?IndexOfKMin(const?T?*x,?int?x_size,?int?k);??

//實(shí)現(xiàn)查找數(shù)組中第K個(gè)最小元下標(biāo)的功能函數(shù)??

template<typename?T>??

int?TheKMin(const?T?*x,?int?*track,?int?left,?int?right,?int?k);??

template<typename?T>??

int?IndexOfKMin(const?T?*x,?int?x_size,?int?k)??

{??

????//判斷k的值是否過大，即超過數(shù)組的大小??

????//若是則返回下標(biāo)-1，主要是為了防止無效的遞歸??

????if(x_size?<?k)??

????????return?-1;??

????//創(chuàng)建一個(gè)跟蹤數(shù)組，其內(nèi)容為原數(shù)組中元素的下標(biāo)，??

????//用于記錄元素的交換（即代替元素的交換）??

????//按順序以track數(shù)組中的數(shù)據(jù)為下標(biāo)訪問元素，訪問順序與上一方法相同??

????int?*track?=?new?int[x_size];??

????for(int?i?=?0;?i?<?x_size;?++i)?//初始化跟蹤數(shù)組，其值與下標(biāo)值相對(duì)應(yīng)??

????????track[i]?=?i;??

????int?i?=?TheKMin(x,?track,?0,?x_size-1,?k);??

????delete?[]track;??

????return?i;??

}??

template<typename?T>??

int?TheKMin(const?T?*x,?int?*track,?int?left,?int?right,?int?k)??

{??

????//取數(shù)組最后一個(gè)元素為樞紐??

????T?centre?=?x[track[right]];??

????int?i?=?left;??

????int?j?=?right?-?1;??

????while(true)??

????{??

????????//從前向后掃描，找到第一個(gè)小于樞紐的值，??

????????//在到達(dá)數(shù)組末尾前，必定結(jié)束循環(huán),因?yàn)樽詈笠粋€(gè)值為centre??

????????//注意此時(shí)的數(shù)據(jù)的下標(biāo)不是i，而是track[i]??

????????while(x[track[i]]?<?centre)??

????????????++i;??

????????//從后向前掃描時(shí)要檢查下標(biāo)，防止數(shù)組越界??

????????while(j?>=?left?&&?x[track[j]]?>?centre)??

????????????--j;??

????????//如果沒有完成一趟交換，則交換，注意，是交換跟蹤數(shù)組的值??

????????if(i?<?j)??

????????????Swap(track[i],?track[j]);??

????????else??

????????????break;??

????}??

????//把樞紐放在正確的位置??

????Swap(track[i],?track[right]);??

????//如果此時(shí)centre的位置剛好為k，則centre為第k個(gè)最小的數(shù)，??

????//返回其在真實(shí)數(shù)組中的下標(biāo)，即track[i]??

????if(i+1?==?k)??

????????return?track[i];??

????else?if(i+1?<?k)??

????{??

????????//如果此時(shí)centre的位置比k前,遞歸地在其右邊尋找??

????????TheKMin(x,?track,?i+1,?right,?k);??

????}??

????else??

????{??

????????//如果此時(shí)centre的位置比k后,遞歸地在其左邊尋找??

????????TheKMin(x,?track,?left,?i-1,?k);??

????}??

}??

代碼說明：

從上面的代碼，我們可以看出，這個(gè)函數(shù)是返回?cái)?shù)組中的第k個(gè)最小元的下標(biāo)，所以當(dāng)k不合理時(shí)，就可以返回-1來表示這個(gè)錯(cuò)誤，同時(shí)，它使用了一個(gè)跟蹤數(shù)組，track數(shù)組中的內(nèi)容，實(shí)質(zhì)是原數(shù)組中數(shù)據(jù)的一個(gè)索引，利用跟蹤數(shù)組的元素的交換來代替了原數(shù)組元素的交換，因?yàn)樵摳檾?shù)組的數(shù)據(jù)類型是int，所以其交換速度相當(dāng)快，從而解決了上面提到的兩個(gè)問題。

從上面的代碼，我們也可以看到，其時(shí)間復(fù)雜度與前面的實(shí)現(xiàn)是一樣的，也為O(N)，但是，這個(gè)實(shí)現(xiàn)方法卻帶來了一定的空間開銷，它開辟了一個(gè)與原數(shù)組元素個(gè)數(shù)相等的一維數(shù)組，用于跟蹤原數(shù)組中的元素的交換情況。

至于在實(shí)際中，要使用哪一種算法，取決于使用者的需要！

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的求数组中第k个最小数的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。