JavaScript 未排序数组中第 k 个最小/最大元素 预期线性时间

如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。未排序数组中第 k 个最小/最大元素 预期线性时间(K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time)给定一个由不同整数组成的数组和一个整数 k其中 k 小于数组的大小任务是找到数组中第k小的元素。例如输入arr [7, 10, 4, 3, 20, 15] k 3输出7解释排序后的数组为 [3, 4, 7, 10, 15, 20]因此第三小的元素是 7。输入arr [7, 10, 4, 3, 20, 15] k 4输出10解释排序后的数组为 [3, 4, 7, 10, 15, 20]因此第 4 小的元素是 10。请注意解决“无序数组中最小/最大元素”问题有多种方法。本文讨论的方案在实践中效果最佳。无序数组中最小/最大元素C 第k个最小元素 C 第k个最小元素(K’th Smallest Element)-CSDN博客C# 第k个最小元素 C# 第k个最小元素(K’th Smallest Element)-CSDN博客Java 第k个最小元素 Java 第k个最小元素(K’th Smallest Element)-CSDN博客Python 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051049JavaScript 第k个最小元素 https://blog.csdn.net/hefeng_aspnet/article/details/163051180其思路是使用随机枢轴选择来划分数组通过专注于第 k 个元素所在的子数组来缩小搜索空间。循序渐进的方法随机选择枢轴元素随机选择一个元素作为枢轴元素。这有助于避免某些情况下的最坏情况例如数组已排序时。分区重新排列数组使所有小于枢轴元素的元素位于左侧所有大于枢轴元素的元素位于右侧。递归搜索枢轴元素确定位置后如果其索引与第 n 次比较相等则它是第 K 个大元素。否则根据与第 n 次-k 比较的结果递归地在相应的分区左侧或右侧中搜索-k。// JavaScript program to find K’th Smallest/// Largest Element in Unsorted Array// Partition function: Rearranges elements// around a pivot (last element)function partition(arr, l, r) {let x arr[r];let i l;// Iterate through the subarrayfor (let j l; j r - 1; j) {// Move elements pivot to the left partitionif (arr[j] x) {[arr[i], arr[j]] [arr[j], arr[i]];i;}}// Place the pivot in its correct position[arr[i], arr[r]] [arr[r], arr[i]];return i;}// Randomizes the pivot to avoid worst-case performancefunction randomPartition(arr, l, r) {let n r - l 1;let pivot Math.floor(Math.random() * n);[arr[l pivot], arr[r]] [arr[r], arr[l pivot]];return partition(arr, l, r);}// function to find the kth smallest element using QuickSelectfunction quickSelect(arr, l, r, k) {// Check if k is within the valid range of the current subarrayif (k 0 k r - l 1) {// Partition the array and get the pivots final positionlet pos randomPartition(arr, l, r);// If pivot is the kth element, return itif (pos - l k - 1)return arr[pos];// If pivots position is larger than k, search left subarrayif (pos - l k - 1)return quickSelect(arr, l, pos - 1, k);// Otherwise, search right subarray and adjust k// (k is reduced by the size of the left partition)return quickSelect(arr, pos 1, r, k - (pos - l 1));}// Return Infinity for invalid k (error handling)return Infinity;}function kthSmallest(arr, k) {let n arr.length;return quickSelect(arr, 0, n - 1, k);}let arr [12, 3, 5, 7, 4, 19, 26];let k 3;console.log(kthSmallest(arr, k));输出5时间复杂度O(n)。上述解决方案的最坏情况时间复杂度仍然是 O(n² )。在最坏情况下随机函数可能总是选择一个角点元素。然而平均情况时间复杂度为 O(n²) O(n)。分析中的假设是随机数生成器生成输入范围内任意数字的概率均等。辅助空间O(1)因为使用了常量变量。即使最坏情况下的时间复杂度是二次方的但这种解决方案在实践中效果最佳。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。