題目：

給定線性序集中n個元素和一個整數k，其中1<=k<=n，要求找出這n個元素中第k小的元素。

?

如果將這n個元素線性序排列時，如果不存在重復的數或者求第k個元素的時候，那么第k個位置即為要找的元素。

當k = 1時，要找的就是最小值；而當k = n時，則要找的則是最大值。

憑借著快速排序中的劃分函數，可以實現上面的功能。

對于序列a[p : q]，分治算法randomizedSelect會隨機選擇一個值作為基準值(pivot)，在劃分之后得到的i，它為基準值所在序列的索引，而基準值把整個序列分成了三部分：分別是小于等于基準值的 a[p: i] 以及基準值 a[ i ] 和大于等于基準值的 a[ i+1 : r ]。

1.求第k個元素

1.1 遞歸版本

/*** 模仿快速排序對數組進行遞歸劃分，并對其一子數組遞歸處理得到第k小元素* @param nums: 數組* @param start: 起始索引 基準值* @param end: 結束索引* @param k: 第k個元素的索引* @return: 返回第k個元素的值 */ template<class Type> Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {if (start == end)return nums[start];//隨機選擇一個基準值int i = randomPartition(nums, start, end);int rank = i - start + 1;if (k == rank)return nums[i];//左邊else if (k < rank)return randomizedSelect(nums, start, i - 1, k);elsereturn randomizedSelect(nums, i + 1, end, k - rank); }

注：randomPartition中除了形參由Type nums[]改為了vector<Type> nums外，其余不變。randomizedSelect函數會在每次都丟棄一半的值。

---

快速排序是對冒泡排序的改進，所以它也有著冒泡排序的特點：每次劃分后的基準值就是它的最終位置。在randomizedSelect函數中，為了得到基準值的位置，由start和基準值i的位置得到了當前基準值的排名，即

int rank = i - start + 1;

接著就可以判斷k == rank，如果相等的話，那么直接返回該值即可；如果k < rank，則表示第k個值在左半部分，否則則在右半部分。如果在右半部分的話，由于已經知道了?i?的位置為rank，所以在換到右半部分的時候，還應該讓k=k-rank。

1.2 非遞歸版本

由遞歸形式改為非遞歸形式，一般會用到循環，有的還會使用到棧。

template<class Type> Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {while (start <= end) {if (start == end)return nums[start];//隨機選擇一個基準值int i = randomPartition(nums, start, end);int rank = i - start + 1;if (k == rank)return nums[i];//左邊else if (k < rank) {end = i - 1;}else {start = i + 1;k = k - rank;}}return nums[start]; }

代碼思路和上面的相同。

2. 求第k小元素

求第k小元素主要考慮的就是重復值的處理。這里給出的解決辦法是在每次按照基準值分成三部分的時候，把兩側的與基準值相同的值聚合到一起，這里需要知道相同值的起始索引left和個數count，之后一次遍歷知道左半部分總共有多少不重復的值rank。

首先，我們可以根據rank就是left的真實位置，然后可以判斷rank == left，如果相等的話，則nums[left]就是第k小元素；如果k < rank，那么k一定散落在左半部分；否則則散落在右半部分。另外，還可以完全去掉基準值和它的相同值們。

其他用到的函數不變，主要改變的就是randomizedSelect函數。

/*** 模仿快速排序對數組進行遞歸劃分，并對其一子數組遞歸處理得到第k小元素* @param nums: 數組* @param start: 起始索引 基準值* @param end: 結束索引* @param k: 第k個元素的索引* @return: 返回第k個元素的值 */ template<class Type> Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {if (start == end)return nums[start];//隨機選擇一個基準值int i = randomPartition(nums, start, end);//聚合與基準值相同的值int rank = 0;int count = together(nums, start, end, i, &rank);if (k == rank)return nums[i];//左邊else if (k < rank)return randomizedSelect(nums, start, i - 1, k);elsereturn randomizedSelect(nums, i + 1 + count, end, k - rank); }

代碼結構和之前類似，相對于之前增加了一個聚合相同值函數together()。其余則不變。

/*** 聚合與基準值相同的值，重新設置基準值為第一個相同值的索引 并返回相同的個數* @param nums: 數組* @param start: 起始索引* @param end: 結束索引* @param pivot: 基準值索引 可能會被重寫* @param left_rank: 左半部分的真實個數* @return :返回了與基準值相同的個數 未算上基準值 */ template<class Type> int together(vector<Type>& nums, int start, int end, int& pivot, int* left_rank = nullptr) {//聚合相同值int left = pivot;int right = pivot;//左邊相同值聚合for (int m = start; m < left && left - 1 > start; m++) {if (nums[m] == nums[pivot]) {nums[m] = nums[--left];nums[left] = nums[pivot];}}//右邊相同值聚合for (int m = end; m > right && right + 1 < end; m--) {if (nums[m] == nums[pivot]) {nums[m] = nums[++right];nums[right] = nums[pivot];}}set<Type> unique;//基準值的真實排名int rank = 1;for (int m = start; m < pivot; m++) {if (nums[m] != nums[pivot] && unique.find(nums[m]) == unique.end()) {unique.insert(nums[m]);rank++;}}//重寫基準值pivot = left;if (left_rank != nullptr)* left_rank = rank;return right - left; }

對于聚合函數together而言，它每次都會遍歷nums[start: end]一遍多一點。

前兩個循環是為了聚合相同值到一塊，第三個循環是為了確定nums[left]的真實排名，這里使用到了c++提供的集合庫#include<set>，通過它來確定不重復的值有多少。

接下來則可以簡單測試一下：

int main() {vector<int> a = { 4, 2, 6, 7, 5, 3};int len = a.size();int k = 5;int value = randomizedSelect(a, 0, len - 1, k);cout << value << endl;for (int i = 0; i < len; i++)cout << a[i] << " ";cout << endl;return 0; }

改進

按照之前的思路，在使用partition函數后，會再有一個聚合相同值并且獲取真正排名的together，其實有關于聚合的功能可以合并到partition函數之中，把相同的值分散在最左邊和最右邊。

假設有數組?nums = { 2, 1, 3, 2, 5, 2, 4 }，以nums[0]為基準值，那么在第一次partition后，nums的值為{2, 2} {1, 2, 5, 3, 4} {}，

左右兩邊都會聚合與基準值相同的值。

/*** 對a[p:r]進行劃分 擴展兩個區域a[p:i]和a[j:r]* @param nums: 數組* @param start: 基準值索引 在這里也是第一個值的索引* @param end: 數組最后一個值的索引* @return: 基準值所在的索引 */ template<class Type> int partition(vector<Type>& nums, int start, int end, int* pLeft, int* qRight) {int left = start, right = end + 1;int p = start, q = end + 1;Type x = nums[start];//將 < x的元素交換到左邊區域 > x的元素交換到右邊區域 相等的移動到兩邊while (true) {while (nums[++left] < x && left < end);while (nums[--right] > x);if (left >= right) break;swap(nums[left], nums[right]);if (nums[left] == x) {p++;swap(nums[left], nums[p]);}if (nums[right] == x) {q--;swap(nums[right], nums[q]);}}//nums[start] = nums[right];nums[p] = nums[right];if (nums[p] != x)p--;//基準值放在最終位置nums[right] = x;if (pLeft) *pLeft = p;if (qRight) *qRight = q;return right; }

在新的partition函數中，它內部還會把相同的值放在最左邊和最右邊，在求得第k小元素時，放在兩邊和聚合在一起區別并不明顯。

template<class Type> int getLeft(vector<Type>& nums, int start, int end) {int index = start;int rank = 0;set<Type> unique;while (index < end) {Type& temp = nums[index];if (unique.find(temp) == unique.end()) {unique.insert(temp);rank++;}index++;}return rank; }

該函數獲取[start, end)的不重復元素的個數。

?

/*** 模仿快速排序對數組進行遞歸劃分，并對其一子數組遞歸處理得到第k小元素* @param nums: 數組* @param start: 起始索引 基準值* @param end: 結束索引* @param k: 第k個元素的索引* @return: 返回第k個元素的值 */ template<class Type> Type randomizedSelect(vector<Type>& nums, int start, int end, int k) {if (start == end)return nums[start];int left = 0, right = 0;//隨機選擇一個基準值int i = randomPartition(nums, start, end, &left, &right);//int i = partition(nums, start, end, &left, &right);//聚合與基準值相同的值int rank = getLeft(nums, left + 1, i) + 1;if (k == rank)return nums[i];//左邊else if (k < rank)return randomizedSelect(nums, left + 1, i - 1, k);elsereturn randomizedSelect(nums, i + 1, right - 1, k - rank); }

?

另外，本代碼通過了牛客網的關于第k小元素的題目。

接下來說說效率，在一般情況下，大約兩次循環能去掉至少一半的值，理論上來說應該要比單純地使用排序算法然后再遍歷要快的。

3.參考

【排序算法】快速排序的分析改進

總結

以上是生活随笔為你收集整理的求第k小元素的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。