目錄例如流程圖示例代碼參考資料如果您喜歡此文章請(qǐng)收藏、點(diǎn)贊、評(píng)論謝謝祝您快樂(lè)每一天。未排序數(shù)組中第 k 個(gè)最小/最大元素 預(yù)期線性時(shí)間(Kth Smallest/Largest Element in Unsorted Array | Set 2 (Expected Linear Time))給定一個(gè)數(shù)組和一個(gè)小于數(shù)組大小的數(shù) k我們需要找到數(shù)組中第 k 大的元素。已知數(shù)組中的所有元素都互不相同。建議您先閱讀以下文章然后再閱讀本文第k個(gè)最小元素C 第k個(gè)最小元素 C 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客C# 第k個(gè)最小元素 C# 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客Java 第k個(gè)最小元素 Java 第k個(gè)最小元素(K’th Smallest Element)_數(shù)組中第k小的數(shù) java-CSDN博客Python 第k個(gè)最小元素 Python 第k個(gè)最小元素(K’th Smallest Element)_最小的 k 個(gè)數(shù) python代碼-CSDN博客JavaScript 第k個(gè)最小元素 JavaScript 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客例如輸入arr[] {7, 10, 4, 3, 20, 15}k 3輸出7輸入arr[] {7, 10, 4, 3, 20, 15}k 4輸出10在上面的文章(第k個(gè)最小元素)中討論了三種不同的解決方案。本文將討論方法 4它主要是對(duì)上面的文章(第k個(gè)最小元素)中討論的方法 3快速選擇的擴(kuò)展。流程圖示例代碼// C# program of above implementationusing System;class GFG{// This function returns kth smallest// element in arr[l..r] using// QuickSort based method. ASSUMPTION:// ALL ELEMENTS IN ARR[] ARE DISTINCTstatic int kthSmallest(int []arr, int l,int r, int k){// If k is smaller than number// of elements in arrayif (k 0 k r - l 1){// Partition the array around last// element and get position of pivot// element in sorted arrayint pos randomPartition(arr, l, r);// If position is same as kif (pos - l k - 1){return arr[pos];}// If position is more, recur// for left subarrayif (pos - l k - 1){return kthSmallest(arr, l, pos - 1, k);}// Else recur for right subarrayreturn kthSmallest(arr, pos 1, r,k - pos l - 1);}// If k is more than number of// elements in arrayreturn 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 rightstatic 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 Codepublic static void Main(){int []arr {12, 3, 5, 7, 4, 19, 26};int n arr.Length, k 3;Console.WriteLine(Kth smallest element is kthSmallest(arr, 0, n - 1, k));}}// this code is contributed by 29AjayKumar輸出Kth smallest element is 5時(shí)間復(fù)雜度 O(N * log N)。輔助空間 O(1)。參考資料C 第k個(gè)最小元素 C 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客C# 第k個(gè)最小元素 C# 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客Java 第k個(gè)最小元素 Java 第k個(gè)最小元素(K’th Smallest Element)_數(shù)組中第k小的數(shù) java-CSDN博客Python 第k個(gè)最小元素 Python 第k個(gè)最小元素(K’th Smallest Element)_最小的 k 個(gè)數(shù) python代碼-CSDN博客JavaScript 第k個(gè)最小元素 JavaScript 第k個(gè)最小元素(K’th Smallest Element)-CSDN博客如果您喜歡此文章請(qǐng)收藏、點(diǎn)贊、評(píng)論謝謝祝您快樂(lè)每一天。