企业官网建设流程全解析

目录

【朴素方法】使用排序——时间复杂度为 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 vector
arr.sort((a, b) => a - b);

// Return k'th element in the sorted vector
return arr[k - 1];
}

//Driver Code
let 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 heap
let pq = new MaxHeap();

// Iterate through the array elements
for (let i = 0; i < arr.length; i++) {

// Push the current element onto the max heap
pq.push(arr[i]);

// If the size of the max heap exceeds k,
//remove the largest element
if (pq.count > k)
pq.pop();
}

return pq.top();
}

// Driver code
let 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 pivot
let pivot = arr[right];
let i = left;

// Traverse the array and move elements <= pivot to the left
for (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 pivot
let pivotIndex = partition(arr, left, right);

// Found k-th smallest
if (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;
}

function kthSmallest(arr, k) {
return quickSelect(arr, 0, arr.length - 1, k - 1);
}

// Driver code
let 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 array
let maxElement = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] > maxElement) maxElement = arr[i];
}

// Create a frequency array
let 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 smallest
let 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 element
return i;
}
}
}
return -1;
}

// Driver Code
let 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)。

如果您喜欢此文章，请收藏、点赞、评论，谢谢，祝您快乐每一天。