Java 第k个最小元素(K’th Smallest Element)

目录【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)【替代方案 1】使用快速选择【替代方案 2】使用计数排序如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。给定一个整数数组arr[]和元素个数k求数组中第 k 小的元素。注意k 始终小于数组的大小。例如输入arr[] [10, 5, 4, 3, 48, 6, 2, 33, 53, 10], k 4输出5说明给定数组中第四小的元素是 5。输入arr[] [7, 10, 4, 3, 20, 15], k 3输出7说明给定数组中第三小的元素是 7。【朴素方法】使用排序——时间复杂度为 O(n log(n))空间复杂度为 O(1)其思路是对给定的数组进行排序并返回索引 k - 1 处的元素。import java.util.Arrays;class GFG {static int kthSmallest(int[] arr, int k) {// Sort the given arrayArrays.sort(arr);// Return kth element in the sorted arrayreturn arr[k - 1];}public static void main(String[] args) {int[] arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;System.out.println(kthSmallest(arr, k));}}输出5【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)其思路是在遍历数组的过程中维护一个大小为 k 的最大堆。该堆始终包含目前为止遇到的 k 个最小元素。如果堆的大小超过 k则移除最大的元素。最终堆中只保留 k 个最小元素。import java.util.PriorityQueue;import java.util.Collections;class GFG {static int kthSmallest(int[] arr, int k){// Create a max heapPriorityQueueInteger pq new PriorityQueue(Collections.reverseOrder());// Iterate through the array elementsfor (int val : arr){// Push the current element onto the max heappq.add(val);// If the size of the max heap exceeds k,// remove the largest elementif (pq.size() k)pq.poll();}// Return the kth smallest element (top of the max heap)return pq.peek();}public static void main(String[] args){int[] arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;System.out.println(kthSmallest(arr, k));}}输出5【替代方案 1】使用快速选择主要思路是利用快速选择QuickSelect函数找到第 k 大元素。具体做法是选择一个基准元素然后将数组分割成多个部分使得大于基准元素的元素位于左侧小于基准元素的元素位于右侧。如果基准元素最终位于索引 k-1 处则该元素即为第 k 大元素。否则我们递归地仅在包含第 k 大元素的左侧或右侧部分进行搜索。class GFG {static int partition(int[] arr, int left, int right) {// Choose the last element as pivotint pivot arr[right];int i left;// Traverse the array and move elements pivot to the leftfor(int j left; j right; j) {if(arr[j] pivot) {// Swap current element with element at iint temp arr[i];arr[i] arr[j];arr[j] temp;i;}}// Place the pivot in its correct positionint temp arr[i];arr[i] arr[right];arr[right] temp;return i;}static int quickSelect(int[] arr, int left, int right, int k) {if(left right) {// Partition around pivotint pivotIndex partition(arr, left, right);// Found k-th smallestif(pivotIndex k) return arr[pivotIndex];else if(pivotIndex k)return quickSelect(arr, left, pivotIndex - 1, k);else return quickSelect(arr, pivotIndex 1, right, k);}return -1;}static int kthSmallest(int[] arr, int k) {return quickSelect(arr, 0, arr.length-1, k-1);}public static void main(String[] args) {int[] arr {10,5,4,3,48,6,2,33,53,10};int k 4;System.out.println(kthSmallest(arr, k));}}输出5时间复杂度 最坏情况下为O(n² )但平均时间为 O(n log n)且性能优于基于优先级队列的算法。辅助空间 最坏情况下递归调用栈为 O(n)。平均而言O(log n)。【替代方案 2】使用计数排序主要思路是利用计数排序的频率计数来跟踪有多少元素小于或等于每个值然后直接从这些累积计数中识别出第 K 小的元素而无需对数组进行完全排序。注意这种方法在元素范围较小时特别有效因为我们声明的数组大小为最大元素个数。如果元素范围非常大计数排序方法可能并非最有效的选择。class GFG {static int kthSmallest(int[] arr, int k) {// First, find the maximum element in the arrayint maxElement arr[0];for (int i 1; i arr.length; i) {if (arr[i] maxElement) {maxElement arr[i];}}// Create an array to store the frequency of each elementint[] freq new int[maxElement 1];for (int i 0; i arr.length; i) {freq[arr[i]];}// Keep track of the cumulative frequency of elementsint count 0;for (int i 0; i maxElement; i) {if (freq[i] ! 0) {count freq[i];if (count k) {// If we have seen k or more elements,// return the current elementreturn i;}}}return -1;}public static void main(String[] args) {int[] arr {10, 5, 4, 3, 48, 6, 2, 33, 53, 10};int k 4;System.out.println(kthSmallest(arr, k));}}输出5时间复杂度 O(n maxElement)其中 maxElement 为数组中的最大元素。辅助空间 O(maxElement)。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。