未排序數組中第 K 個最小/最大元素| 系列 1 · GeeksForGeeks 中文系列教程

# 未排序數組中第 K 個最小/最大元素| 系列 1 > 原文： [https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/](https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/) 給定一個數組和一個數`k`（其中`k`小于數組的大小），我們需要找到給定數組中第`k`個最小的元素。假定有 11 個數組元素是不同的。 **示例**： ``` 輸入: arr [] = {7, 10, 4, 4, 3, 20, 15} k = 3 輸出: 7 輸入: arr [] = {7, 10, 4, 3, 20, 15} k = 4 輸出: 10 ``` 我們已經討論了類似的[問題來打印 k 個最大元素](https://www.geeksforgeeks.org/k-largestor-smallest-elements-in-an-array/)。 **方法 1（簡單解決方案）** 一個簡單的解決方案是使用`O(N log N)`排序算法對給定數組進行排序，例如[合并排序](http://geeksquiz.com/merge-sort/)， [堆排序](http://geeksquiz.com/heap-sort/)等，并返回已排序數組中索引`k-1`處的元素。該解決方案的時間復雜度為`O(N log N)` ## C++ ```cpp // Simple C++ program to find k'th smallest element #include <algorithm> #include <iostream> using namespace std; // Function to return k'th smallest element in a given array int kthSmallest(int arr[], int n, int k) { ????// Sort the given array ????sort(arr, arr + n); ????// Return k'th element in the sorted array ????return arr[k - 1]; } // Driver program to test above methods int main() { ????int arr[] = { 12, 3, 5, 7, 19 }; ????int n = sizeof(arr) / sizeof(arr[0]), k = 2; ????cout << "K'th smallest element is " << kthSmallest(arr, n, k); ????return 0; } ``` ## Java ```java // Java code for kth smallest element // in an array import java.util.Arrays; import java.util.Collections; class GFG { ????// Function to return k'th smallest ????// element in a given array ????public static int kthSmallest(Integer[] arr, ??????????????????????????????????int k) ????{ ????????// Sort the given array ????????Arrays.sort(arr); ????????// Return k'th element in ????????// the sorted array ????????return arr[k - 1]; ????} ????// driver program ????public static void main(String[] args) ????{ ????????Integer arr[] = new Integer[] { 12, 3, 5, 7, 19 }; ????????int k = 2; ????????System.out.print("K'th smallest element is " + kthSmallest(arr, k)); ????} } // This code is contributed by Chhavi ``` ## Python3 ```py # Python3 program to find k'th smallest # element? # Function to return k'th smallest? # element in a given array? def kthSmallest(arr, n, k): ????# Sort the given array? ????arr.sort() ????# Return k'th element in the? ????# sorted array? ????return arr[k-1] # Driver code if __name__=='__main__': ????arr = [12, 3, 5, 7, 19] ????n = len(arr) ????k = 2 ????print("K'th smallest element is", ??????????kthSmallest(arr, n, k)) # This code is contributed by? # Shrikant13 ``` ## C# ```cs // C# code for kth smallest element // in an array using System; class GFG { ????// Function to return k'th smallest ????// element in a given array ????public static int kthSmallest(int[] arr, ??????????????????????????????????int k) ????{ ????????// Sort the given array ????????Array.Sort(arr); ????????// Return k'th element in ????????// the sorted array ????????return arr[k - 1]; ????} ????// driver program ????public static void Main() ????{ ????????int[] arr = new int[] { 12, 3, 5, ????????????????????????????????7, 19 }; ????????int k = 2; ????????Console.Write("K'th smallest element" ??????????????????????+ " is " + kthSmallest(arr, k)); ????} } // This code is contributed by nitin mittal. ``` ## PHP ```php <?php // Simple PHP program to find? // k'th smallest element // Function to return k'th smallest // element in a given array function kthSmallest($arr, $n, $k) { ????// Sort the given array ????sort($arr); ????// Return k'th element? ????// in the sorted array ????return $arr[$k - 1]; } ????// Driver Code ????$arr = array(12, 3, 5, 7, 19); ????$n =count($arr); ????$k = 2; ????echo "K'th smallest element is ", kthSmallest($arr, $n, $k); // This code is contributed by anuj_67\. ?> ``` **輸出**： ``` K'th smallest element is 5 ``` **方法 2（使用最小堆 – HeapSelect）** 我們發現時間復雜度中的第`k`個最小元素要好于`O(N log N)`。一個簡單的優化方法是創建給定`n`個元素的[最小堆](http://geeksquiz.com/binary-heap/)，并調用`k`次`extractMin()`。以下是上述方法的 C++ 實現。 ``` // A C++ program to find k'th smallest element using min heap #include <climits> #include <iostream> using namespace std; // Prototype of a utility function to swap two integers void swap(int* x, int* y); // A class for Min Heap class MinHeap { ????int* harr; // pointer to array of elements in heap ????int capacity; // maximum possible size of min heap ????int heap_size; // Current number of elements in min heap public: ????MinHeap(int a[], int size); // Constructor ????void MinHeapify(int i); // To minheapify subtree rooted with index i ????int parent(int i) { return (i - 1) / 2; } ????int left(int i) { return (2 * i + 1); } ????int right(int i) { return (2 * i + 2); } ????int extractMin(); // extracts root (minimum) element ????int getMin() { return harr[0]; } // Returns minimum }; MinHeap::MinHeap(int a[], int size) { ????heap_size = size; ????harr = a; // store address of array ????int i = (heap_size - 1) / 2; ????while (i >= 0) { ????????MinHeapify(i); ????????i--; ????} } // Method to remove minimum element (or root) from min heap int MinHeap::extractMin() { ????if (heap_size == 0) ????????return INT_MAX; ????// Store the minimum vakue. ????int root = harr[0]; ????// If there are more than 1 items, move the last item to root ????// and call heapify. ????if (heap_size > 1) { ????????harr[0] = harr[heap_size - 1]; ????????MinHeapify(0); ????} ????heap_size--; ????return root; } // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified void MinHeap::MinHeapify(int i) { ????int l = left(i); ????int r = right(i); ????int smallest = i; ????if (l < heap_size && harr[l] < harr[i]) ????????smallest = l; ????if (r < heap_size && harr[r] < harr[smallest]) ????????smallest = r; ????if (smallest != i) { ????????swap(&harr[i], &harr[smallest]); ????????MinHeapify(smallest); ????} } // A utility function to swap two elements void swap(int* x, int* y) { ????int temp = *x; ????*x = *y; ????*y = temp; } // Function to return k'th smallest element in a given array int kthSmallest(int arr[], int n, int k) { ????// Build a heap of n elements: O(n) time ????MinHeap mh(arr, n); ????// Do extract min (k-1) times ????for (int i = 0; i < k - 1; i++) ????????mh.extractMin(); ????// Return root ????return mh.getMin(); } // Driver program to test above methods int main() { ????int arr[] = { 12, 3, 5, 7, 19 }; ????int n = sizeof(arr) / sizeof(arr[0]), k = 2; ????cout << "K'th smallest element is " << kthSmallest(arr, n, k); ????return 0; } ``` **輸出**： ``` K'th smallest element is 5 ``` 該解決方案的時間復雜度為`O(n + kLogn)`。 **方法 3（使用最大堆）** 我們也可以使用最大堆來找到第`k`個最小元素。以下是算法。 1）建立給定數組的前`k`個元素（`arr[0]`至`arr[k-1]`）的最大堆 MH 2）對于每個元素，在第`k`個元素之后（`arr[k]`至`arr[n-1]`），將其與 MH 的根進行比較。 ……a）如果元素小于根，則將其設為根并為 MH 調用建堆 ……b）否則將其忽略。 //步驟 2 為`O((n-k) * logk)` 3）最后，MH 的根是第`k`個最小元素。該解決方案的時間復雜度為`O(k + (n-k) * Logk)` 以下是上述算法的 C++ 實現 ``` // A C++ program to find k'th smallest element using max heap #include <climits> #include <iostream> using namespace std; // Prototype of a utility function to swap two integers void swap(int* x, int* y); // A class for Max Heap class MaxHeap { ????int* harr; // pointer to array of elements in heap ????int capacity; // maximum possible size of max heap ????int heap_size; // Current number of elements in max heap public: ????MaxHeap(int a[], int size); // Constructor ????void maxHeapify(int i); // To maxHeapify subtree rooted with index i ????int parent(int i) { return (i - 1) / 2; } ????int left(int i) { return (2 * i + 1); } ????int right(int i) { return (2 * i + 2); } ????int extractMax(); // extracts root (maximum) element ????int getMax() { return harr[0]; } // Returns maximum ????// to replace root with new node x and heapify() new root ????void replaceMax(int x) ????{ ????????harr[0] = x; ????????maxHeapify(0); ????} }; MaxHeap::MaxHeap(int a[], int size) { ????heap_size = size; ????harr = a; // store address of array ????int i = (heap_size - 1) / 2; ????while (i >= 0) { ????????maxHeapify(i); ????????i--; ????} } // Method to remove maximum element (or root) from max heap int MaxHeap::extractMax() { ????if (heap_size == 0) ????????return INT_MAX; ????// Store the maximum vakue. ????int root = harr[0]; ????// If there are more than 1 items, move the last item to root ????// and call heapify. ????if (heap_size > 1) { ????????harr[0] = harr[heap_size - 1]; ????????maxHeapify(0); ????} ????heap_size--; ????return root; } // A recursive method to heapify a subtree with root at given index // This method assumes that the subtrees are already heapified void MaxHeap::maxHeapify(int i) { ????int l = left(i); ????int r = right(i); ????int largest = i; ????if (l < heap_size && harr[l] > harr[i]) ????????largest = l; ????if (r < heap_size && harr[r] > harr[largest]) ????????largest = r; ????if (largest != i) { ????????swap(&harr[i], &harr[largest]); ????????maxHeapify(largest); ????} } // A utility function to swap two elements void swap(int* x, int* y) { ????int temp = *x; ????*x = *y; ????*y = temp; } // Function to return k'th largest element in a given array int kthSmallest(int arr[], int n, int k) { ????// Build a heap of first k elements: O(k) time ????MaxHeap mh(arr, k); ????// Process remaining n-k elements.? If current element is ????// smaller than root, replace root with current element ????for (int i = k; i < n; i++) ????????if (arr[i] < mh.getMax()) ????????????mh.replaceMax(arr[i]); ????// Return root ????return mh.getMax(); } // Driver program to test above methods int main() { ????int arr[] = { 12, 3, 5, 7, 19 }; ????int n = sizeof(arr) / sizeof(arr[0]), k = 4; ????cout << "K'th smallest element is " << kthSmallest(arr, n, k); ????return 0; } ``` **輸出**： ``` K'th smallest element is 12 ``` **方法 4（快速選擇）** 如果在第一步中將[快速排序](http://geeksquiz.com/quick-sort/)用作排序算法，則這是對方法 1 的優化。在快速排序中，我們選擇一個樞軸元素，然后將樞軸元素移動到正確的位置并圍繞該數組對其進行分區。這個想法不是要進行完整的快速排序，而是停在樞軸本身是第`k`個最小元素的位置。同樣，不要針對樞軸的左側和右側重復出現，而是根據樞軸的位置針對其中之一進行重復播放。該方法最壞的情況是時間復雜度為 `O(n^2)`，但平均而言，它的工作時間為`O(n)`。 ## C++ ``` #include <climits> #include <iostream> using namespace std; int partition(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 = partition(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; } // 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; } ```