Java 未排序数组中第 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个最小元素 Python 第k个最小元素(K’th Smallest Element)-CSDN博客JavaScript 第k个最小元素 JavaScript 第k个最小元素(K’th Smallest Element)-CSDN博客其思路是使用随机枢轴选择来划分数组通过专注于第 k 个元素所在的子数组来缩小搜索空间。循序渐进的方法随机选择枢轴元素随机选择一个元素作为枢轴元素。这有助于避免某些情况下的最坏情况例如数组已排序时。分区重新排列数组使所有小于枢轴元素的元素位于左侧所有大于枢轴元素的元素位于右侧。递归搜索枢轴元素确定位置后如果其索引与第 n 次比较相等则它是第 K 个大元素。否则根据与第 n 次-k 比较的结果递归地在相应的分区左侧或右侧中搜索-k。// Java program to find K’th Smallest/// Largest Element in Unsorted Arrayimport java.util.Random;class GfG {// Partition function: Rearranges elements// around a pivot (last element)static int partition(int[] arr, int l, int r) {int x arr[r];int i l;// Iterate through the subarrayfor (int j l; j r - 1; j) {// Move elements pivot to the left partitionif (arr[j] x) {int temp arr[i];arr[i] arr[j];arr[j] temp;i;}}// Place the pivot in its correct positionint temp arr[i];arr[i] arr[r];arr[r] temp;return i;}// Randomizes the pivot to avoid worst-case performancestatic int randomPartition(int[] arr, int l, int r) {Random rand new Random();int n r - l 1;int pivot rand.nextInt(n);int temp arr[l pivot];arr[l pivot] arr[r];arr[r] temp;return partition(arr, l, r);}// function to find the kth smallest element using QuickSelectstatic int quickSelect(int[] arr, int l, int r, int 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 positionint 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 Integer.MAX_VALUE;}static int kthSmallest(int[] arr, int k) {int n arr.length;return quickSelect(arr, 0, n - 1, k);}public static void main(String[] args) {int[] arr {12, 3, 5, 7, 4, 19, 26};int k 3;System.out.println(kthSmallest(arr, k));}}输出5时间复杂度O(n)。上述解决方案的最坏情况时间复杂度仍然是 O(n² )。在最坏情况下随机函数可能总是选择一个角点元素。然而平均情况时间复杂度为 O(n²) O(n)。分析中的假设是随机数生成器生成输入范围内任意数字的概率均等。辅助空间O(1)因为使用了常量变量。即使最坏情况下的时间复杂度是二次方的但这种解决方案在实践中效果最佳。如果您喜欢此文章请收藏、点赞、评论谢谢祝您快乐每一天。

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

相关推荐

Minmax H3本地部署全流程：显存、参数与批量任务实战

宝可梦朱紫悖论草鹿铁斑叶派送全攻略：从交换到培养

Python LSTM实战：量化投资中的时间序列预测与模型调优

更多资讯

工地太忙根本没时间复习考试？电工证考试科目3技巧+上岗必备全攻略

云南电工证培训天数不够用，工地太忙根本没时间复习考试怎么办？

电工证包括家电维修吗？考前押题全攻略来了

电工证办理办理通过率揭秘：学历不高怕报不上名？真实情况全在这

珠海考电工证的地方怎么转证？官方报名入口在这儿

电工证过期时间你知道吗？内部消息告诉你怎么转异地

今日更新

金坛办电工证在哪里？考前押题能帮你少走弯路

怎样查看真假电工证怎么考

史密斯内部电工证值不值得考？怕考不过白交培训费的看过来

本周精选

安监局电工证分数查询怎么查才能知道含金量高不高

新疆电工作业干活累吗良心建议助你避开考不过的坑

中牟县电工证怎么报名外省证能转吗

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？