未排序数组中第 K 个最小/最大元素| 组合 3（最坏情况的线性时间） · GeeksForGeeks 中文系列教程

# 未排序数组中第 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; } ```