# 未排序數組中第 K 個最小/最大元素| 系列 2（預期線性時間） > 原文： [https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time-2/](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-2-expected-linear-time-2/) 我們建議閱讀以下文章，作為該文章的先決條件。 [未排序數組中第`K`個最小/最大元素| 系列 1](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 給定一個數組和一個數`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/) 本文討論了方法 4，它主要是對[先前](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/)帖子中討論的方法 3（QuickSelect）的擴展。 ## C++ ```cpp // C++ implementation of above implementation #include<iostream> #include<climits> #include<cstdlib> using namespace std; int randomPartition(int arr[], int l, int r); // This function returns k'th smallest element in arr[l..r] using // QuickSort based method.? 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) ????{ ????????// Partition the array around last element and get ????????// position of pivot element in sorted array ????????int pos = randomPartition(arr, l, r); ????????// 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 subarray ????????????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; } // Standard partition process of QuickSort().? It considers the last // element as pivot and moves all smaller element to left of it // and greater elements to right int partition(int arr[], int l, int r) { ????int x = arr[r], 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; } int randomPartition(int arr[], int l, int r) { ????int n = r-l+1; ????int pivot = rand() % n; ????swap(&arr[l + pivot], &arr[r]); ????return partition(arr, l, r); } // 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; }?????????????????? ``` ## Java ```java // Java program of above implementation import java.util.Random; public class GFG { // This function returns k'th smallest element in arr[l..r] using // QuickSort based method. ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT ????static 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) { ????????????// Partition the array around last element and get ????????????// position of pivot element in sorted array ????????????int pos = randomPartition(arr, l, r); ????????????// 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 subarray ????????????{ ????????????????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 Integer.MAX_VALUE; ????} ????static void swap(int[] arr, int i, int j) { ????????int temp = arr[i]; ????????arr[i] = arr[j]; ????????arr[j] = temp; ????} // Standard partition process of QuickSort(). It considers the last // element as pivot and moves all smaller element to left of it // and greater elements to right ????static int partition(int arr[], int l, int r) { ????????int x = arr[r], i = l; ????????for (int j = l; j <= r - 1; j++) { ????????????if (arr[j] <= x) { ????????????????swap(arr, i, j); ????????????????i++; ????????????} ????????} ????????swap(arr, i, r); ????????return i; ????} ????static int randomPartition(int arr[], int l, int r) { ????????int n = r - l + 1; ????????int pivot = new Random().nextInt(1); ????????swap(arr, l + pivot, r); ????????return partition(arr, l, r); ????} // Driver program to test above methods ????public static void main(String args[]) { ????????int arr[] = {12, 3, 5, 7, 4, 19, 26}; ????????int n = arr.length, k = 3; ????????System.out.println("K'th smallest element is " + kthSmallest(arr, 0, n - 1, k)); ????} } /*This code is contributed by 29AjayKumar*/ ``` ## Python3 ```py # Python3 implementation of above implementation # This function returns k'th smallest element? # in arr[l..r] using QuickSort based method. # ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT from random import randint def randomPartition(arr, l, r): ????n = r - l + 1 ????pivot = randint(1, 100) % n ????arr[l + pivot], arr[r] = arr[l + pivot], arr[r] ????return partition(arr, l, r) def kthSmallest(arr, l, r, k): ????# If k is smaller than? ????# number of elements in array ????if (k > 0 and k <= r - l + 1): ????????# Partition the array around last element and? ????????# get position of pivot element in sorted array ????????pos = randomPartition(arr, l, r) ????????# If position is same as k ????????if (pos - l == k - 1): ????????????return arr[pos] ????????# If position is more, recur for left subarray ????????if (pos - l > k - 1):? ????????????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 10**9 # Standard partition process of QuickSort().? # It considers the last element as pivot and? # moves all smaller element to left of it # and greater elements to right def partition(arr, l, r): ????x = arr[r] ????i = l ????for j in range(l, r): ????????if (arr[j] <= x): ????????????arr[i], arr[j] = arr[j], arr[i] ????????????i += 1 ????arr[i], arr[r] = arr[r], arr[i] ????return i # Driver Code arr = [12, 3, 5, 7, 4, 19, 26] n = len(arr) k = 3 print("K'th smallest element is",? ???????kthSmallest(arr, 0, n - 1, k)) # This code is contributed by Mohit Kumar ``` ## C# ```cs // C# program of above implementation using System; class GFG? {? // This function returns k'th smallest? // element in arr[l..r] using? // QuickSort based method. ASSUMPTION:? // ALL ELEMENTS IN ARR[] ARE DISTINCT? static 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)? ????{ ????????// Partition the array around last? ????????// element and get position of pivot ????????// element in sorted array? ????????int pos = randomPartition(arr, l, r);? ????????// If position is same as k? ????????if (pos - l == k - 1)? ????????{? ????????????return arr[pos];? ????????}? ????????// If position is more, recur? ????????// for left subarray? ????????if (pos - l > k - 1)? ????????{? ????????????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.MaxValue;? }? static void swap(int[] arr, int i, int j) {? ????int temp = arr[i];? ????arr[i] = arr[j];? ????arr[j] = temp;? }? // Standard partition process of QuickSort().? // It considers the last element as pivot and? // oves all smaller element to left of it? // and greater elements to right? static int partition(int []arr, int l, int r)? {? ????int x = arr[r], i = l;? ????for (int j = l; j <= r - 1; j++) ????{? ????????if (arr[j] <= x)? ????????{? ????????????swap(arr, i, j);? ????????????i++;? ????????}? ????}? ????swap(arr, i, r);? ????return i;? }? static int randomPartition(int []arr, int l, int r) {? ????int n = r - l + 1;? ????int pivot = new Random().Next(1);? ????swap(arr, l + pivot, r);? ????return partition(arr, l, r);? }? // Driver Code public static void Main() {? ????int []arr = {12, 3, 5, 7, 4, 19, 26};? ????int n = arr.Length, k = 3;? ????Console.WriteLine("K'th smallest element is " +? ????????????????????kthSmallest(arr, 0, n - 1, k));? }? }? // his code is contributed by 29AjayKumar ``` **輸出**： ``` K'th smallest element is 5 ``` **參考**： [https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/)