目录【朴素方法】使用排序——时间复杂度为 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 处的元素。function kthSmallest(arr, k){// Sort the given vectorarr.sort((a, b) a - b);// Return kth element in the sorted vectorreturn arr[k - 1];}//Driver Codelet arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10];let k 4;console.log(kthSmallest(arr, k));输出5【预期方法】使用最大堆 - 时间复杂度为 O(n * log(k))空间复杂度为 O(k)其思路是在遍历数组的过程中维护一个大小为 k 的最大堆。该堆始终包含目前为止遇到的 k 个最小元素。如果堆的大小超过 k则移除最大的元素。最终堆中只保留 k 个最小元素。class MaxHeap {constructor() {this.heap [];}get count() {return this.heap.length;}push(val) {this.heap.push(val);let i this.heap.length - 1;while (i 0) {let parent Math.floor((i - 1) / 2);if (this.heap[parent] this.heap[i]) break;// Swap[this.heap[parent], this.heap[i]] [this.heap[i], this.heap[parent]];i parent;}}pop() {if (this.heap.length 0) {console.log(Heap is empty);return -1;}let top this.heap[0];this.heap[0] this.heap[this.heap.length - 1];this.heap.pop();let i 0;while (true) {let left 2 * i 1;let right 2 * i 2;let largest i;if (left this.heap.length this.heap[left] this.heap[largest])largest left;if (right this.heap.length this.heap[right] this.heap[largest])largest right;if (largest i) break;[this.heap[i], this.heap[largest]] [this.heap[largest], this.heap[i]];i largest;}return top;}top() {if (this.heap.length 0) {console.log(Heap is empty);return -1;}return this.heap[0];}}function kthSmallest(arr, k) {// Create a max heaplet pq new MaxHeap();// Iterate through the array elementsfor (let i 0; i arr.length; i) {// Push the current element onto the max heappq.push(arr[i]);// If the size of the max heap exceeds k,//remove the largest elementif (pq.count k)pq.pop();}return pq.top();}// Driver codelet arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10];let K 4;console.log(kthSmallest(arr, K));输出5【替代方案 1】使用快速选择主要思路是利用快速选择QuickSelect函数找到第 k 大元素。具体做法是选择一个基准元素然后将数组分割成多个部分使得大于基准元素的元素位于左侧小于基准元素的元素位于右侧。如果基准元素最终位于索引 k-1 处则该元素即为第 k 大元素。否则我们递归地仅在包含第 k 大元素的左侧或右侧部分进行搜索。function partition(arr, left, right) {// Choose the last element as pivotlet pivot arr[right];let i left;// Traverse the array and move elements pivot to the leftfor (let j left; j right; j) {if (arr[j] pivot) {// Swap current element with element at i[arr[i], arr[j]] [arr[j], arr[i]];i;}}// Place the pivot in its correct position[arr[i], arr[right]] [arr[right], arr[i]];return i;}function quickSelect(arr, left, right, k) {if (left right) {// Partition around pivotlet 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);elsereturn quickSelect(arr, pivotIndex 1, right, k);}return -1;}function kthSmallest(arr, k) {return quickSelect(arr, 0, arr.length - 1, k - 1);}// Driver codelet arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10];let k 4;console.log(kthSmallest(arr, k));输出5时间复杂度 最坏情况下为O(n² )但平均时间为 O(n log n)且性能优于基于优先级队列的算法。辅助空间 最坏情况下递归调用栈为 O(n)。平均而言O(log n)。【替代方案 2】使用计数排序主要思路是利用计数排序的频率计数来跟踪有多少元素小于或等于每个值然后直接从这些累积计数中识别出第 K 小的元素而无需对数组进行完全排序。注意这种方法在元素范围较小时特别有效因为我们声明的数组大小为最大元素个数。如果元素范围非常大计数排序方法可能并非最有效的选择。function kthSmallest(arr, k) {// First, find the maximum element in the arraylet maxElement arr[0];for (let i 1; i arr.length; i) {if (arr[i] maxElement) maxElement arr[i];}// Create a frequency arraylet freq new Array(maxElement 1).fill(0);for (let i 0; i arr.length; i) {freq[arr[i]];}// Track cumulative frequency to find k-th smallestlet count 0;for (let 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;}// Driver Codelet arr [10, 5, 4, 3, 48, 6, 2, 33, 53, 10];let k 4;console.log(kthSmallest(arr, k));输出5时间复杂度 O(n maxElement)其中 maxElement 为数组中的最大元素。辅助空间 O(maxElement)。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。