# 未排序數組中第 K 個最小/最大元素| 組合 3（最壞情況的線性時間） > 原文： [https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-linear-time/) 我們建議閱讀以下文章，作為此文章的先決條件。 [未排序數組中第`K`個最小/最大元素| 集合 1](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) [未排序數組中第`K`個最小/最大元素| 系列 2（預期線性時間）](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/) 給定一個數組和一個數字`k`，其中`k`小于數組的大小，我們需要找到給定數組中第`k`個最小的元素。 假定所有數組元素都是不同的。 **示例**： ``` Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 Output: 7 Input: arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output: 10 ``` 在[之前的文章](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/)中，我們討論了一種預期的線性時間算法。 在這篇文章中，討論了最壞情況的線性時間方法。 *此新方法中的想法類似于`quickSelect()`，我們通過選擇以平衡方式對數組進行分割的樞軸來獲得最壞情況的線性時間（一側上的元素很少，而另一側的元素很多）*。 在以平衡方式分割數組之后，我們采用與`quickSelect()`中相同的步驟來確定是在數據透視表的左側還是右側移動。 以下是完整的算法。 > `kthSmallest(arr[0..n-1], k)` > **1）**將`arr[]`分成`?n/5?`個組，每個組的大小為 5，但 可能最后一組的元素少于 5 個。 > > **2）**對上面創建的`n / 5`個分組進行排序，并找到所有分組的中位數。 創建一個輔助數組`median[]`，并將所有`?n/5?`個組的中值存儲在該中值數組中。 > > //遞歸調用此方法以找到中位數`[0..?n/5?-1]` > **3）** `medOfMed = kthSmallest(median [0..?n/5?-1]], ?n/10?)` > > **4）**在`medOfMed`周圍劃分`arr[]`并獲取其位置。 > `pos = partition(arr, n, medOfMed)` > > **5）**如果`pos == k`，則返回`medOfMed` > **6）**如果`pos > k`，則返回`kthSmallest(arr[l..pos-1], k)` > **7）**如果`pos < k`返回`kthSmallest(arr[pos + 1..r], k-pos + 1-1)` 在上述算法中，最后 3 個步驟與[先前文章](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time/)中的算法相同。 前四個步驟用于獲得對數組進行分區的一個好方法（以確保樞軸兩邊沒有太多元素）。 以下是上述算法的實現。 ## C++ ```cpp // C++ implementation of worst case linear time algorithm // to find k'th smallest element #include<iostream> #include<algorithm> #include<climits> using namespace std; int partition(int arr[], int l, int r, int k); // A simple function to find median of arr[].? This is called // only for an array of size 5 in this program. int findMedian(int arr[], int n) { ????sort(arr, arr+n);? // Sort the array ????return arr[n/2];?? // Return middle element } // Returns k'th smallest element in arr[l..r] in worst case // linear time. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT int kthSmallest(int arr[], int l, int r, int k) { ????// If k is smaller than number of elements in array ????if (k > 0 && k <= r - l + 1) ????{ ????????int n = r-l+1; // Number of elements in arr[l..r] ????????// Divide arr[] in groups of size 5, calculate median ????????// of every group and store it in median[] array. ????????int i, median[(n+4)/5]; // There will be floor((n+4)/5) groups; ????????for (i=0; i<n/5; i++) ????????????median[i] = findMedian(arr+l+i*5, 5); ????????if (i*5 < n) //For last group with less than 5 elements ????????{ ????????????median[i] = findMedian(arr+l+i*5, n%5);? ????????????i++; ????????}???? ????????// Find median of all medians using recursive call. ????????// If median[] has only one element, then no need ????????// of recursive call ????????int medOfMed = (i == 1)? median[i-1]: ?????????????????????????????????kthSmallest(median, 0, i-1, i/2); ????????// Partition the array around a random element and ????????// get position of pivot element in sorted array ????????int pos = partition(arr, l, r, medOfMed); ????????// If position is same as k ????????if (pos-l == k-1) ????????????return arr[pos]; ????????if (pos-l > k-1)? // If position is more, recur for left ????????????return kthSmallest(arr, l, pos-1, k); ????????// Else recur for right subarray ????????return kthSmallest(arr, pos+1, r, k-pos+l-1); ????} ????// If k is more than number of elements in array ????return INT_MAX; } void swap(int *a, int *b) { ????int temp = *a; ????*a = *b; ????*b = temp; } // It searches for x in arr[l..r], and partitions the array? // around x. int partition(int arr[], int l, int r, int x) { ????// Search for x in arr[l..r] and move it to end ????int i; ????for (i=l; i<r; i++) ????????if (arr[i] == x) ???????????break; ????swap(&arr[i], &arr[r]); ????// Standard partition algorithm ????i = l; ????for (int j = l; j <= r - 1; j++) ????{ ????????if (arr[j] <= x) ????????{ ????????????swap(&arr[i], &arr[j]); ????????????i++; ????????} ????} ????swap(&arr[i], &arr[r]); ????return i; } // Driver program to test above methods int main() { ????int arr[] = {12, 3, 5, 7, 4, 19, 26}; ????int n = sizeof(arr)/sizeof(arr[0]), k = 3; ????cout << "K'th smallest element is " ?????????<< kthSmallest(arr, 0, n-1, k); ????return 0; } ```