`
sunlujing
  • 浏览: 177623 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

最坏情况O(N) 求数组中第K 大的元素。

阅读更多
求数组中第K的元素的一般方法就是使用快速排序的划分,
Partion(seq,start,end) = p, 如果p=k 则ok。如果p >k 
则在start, p -1的区间里找第K大的数,Partion(seq,start,p-1)
否则partion(seq,p+1,end)
算法的平均时间复杂度为O(N),最坏情况为N^2,即每次划分把数组变为为(n-1) 和1的两断.
对此算法导论上给出了一个最坏情况下为O(N)的算法
该算法就是每次partion的时候找到一个好的划分,用中位数的中位数作为pivot。
把数组分为 N/5组,每组插入排序之后求得中位数,共 N/5 个中位数,对这N/5 中位数,使用同样过程再排序再求中位数(递归完成),最后求得N/5的中位数的中位数 作为最佳pivot,如下。
private static int  getPerfectPivot (int[]seq,int start,int end){
if(start==end){
return seq[start];
}
int groups = (end-start+1)%5==0?(end-start+1)/5:(end-start+1)/5+1;
int[] group_median = new int[groups];
for(int i=0; i < groups;i++){
int from = start+i*5;
int to = (from+5 < end)?(from+5):end;
for(int k=from+1;k<to;k++){
if(seq[k] < seq[k+1]){
//sawp
int temp = seq[k];
seq[k] = seq[k+1];
seq[k+1] =temp;
}
}
group_median[i] = seq[(from+to)/2];
}
return getPerfectPivot(group_median,0,groups-1);
}
 
稍微修改Partion的过程,即可获得O(N)复杂度的算法
private static int partionByMedian(int start,int end, int[]seq){
int pivot =  getPerfectPivot (seq,start,end);
//这里不再使用最后一个元素,也不使用rand随机设定一个元素
int swap_index = start -1;
for(int i = start;i<end;i++){
if(seq[i] <pivot){
swap_index++;
int temp = seq[swap_index];
seq[swap_index] = seq[i];
seq[i] = temp;
}
if(seq[i]==pivot && seq[end]!=pivot){
int temp = seq[i];
seq[i] = seq[end];
seq[end] = temp;
i--;
}
                //这一段是找出最好的pivot在数组中的位置并放到末尾。
}
swap_index++;
seq[end] = seq[swap_index];
seq[swap_index] = pivot;
return swap_index;
}
 
 
整个算法的执行时间可证明为O(N)参考算法导论。
1
1
分享到:
评论

相关推荐

    逆序对问题

    请考虑一个最坏情况O(nlogn)的算法确定n个元素的逆序对数目。 注意此题请勿用O(n^2)的简单枚举去实现。 并思考如下问题: (1)怎样的数组含有最多的逆序对?最多的又是多少个呢? (2)插入排序的运行时间和数组中...

    计算机二级公共基础知识

    1. 算法的基本概念 利用计算机算法为计算机解题的过程实际上是在实施某种算法。 (1)算法的基本特征 算法一般具有4个基本特征:可行...对于长度为n的有序线性表,在最坏情况下,二分法查找只需比较log2n次, 二级公共...

    求出乱序中最小k的位置-java

    快速排序算法,时间复杂度o(nlogn),但是不稳定最坏的时候能达到O(n^2) 题目:找出乱序中最小k的位置 如何从N个乱序数据中,快速地找出第K小的数? 有数据 2,6,3,5,7,9,找出最小k的位置,k为用户输入(不能超过数组...

    算法设计与分析 java(包含几种经典算法)

    要求算法在最坏情况下耗时O(n),且只用到O(1)的辅助空间。 2.在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分...

    《数据结构 1800题》

    其中 n为正整数,则最后一行的语句频度在最坏情况下是(D ) 郴州都市网 www.0735.cc郴州人才网 www.CZHR.com www.989.org 《数据结构 1800题》 A. O(n) B. O(nlogn) C. O(n3) D. O(n2) 【南京理工大学 ...

    数据结构(C++)有关练习题

    D. *建立函数create:根据一维数组a[n]建立一个单链表,使单链表中各元素的次序与a[n]中各元素的次序相同,要求该程序的时间复杂度为O(n)。 E. *整理函数tideup:在非递减有序的单链表中删除值相同的多余...

    数据结构题

    8. 快速排序在最坏情况下的时间复杂度为( )。 A.O(log2n) B.O(nlog2n) C.0(n) D.0(n2) 9. 从二叉搜索树中查找一个元素时,其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 10. 栈和队列的共同...

    lrucacheleetcode-Leetcode_Playground:破解编码面试和leetcode问题的解决方法

    lru缓存leetcode 力码游乐场 破解编码面试问题和Leetcode问题的解决方法 问题 给定一个非空的整数数组,每个元素出现两次,除了一个。 找到那一个。 快乐号 ...第一个坏版本 珠宝和石头(基于套装的

    南宁师范师大学818计算机基础2017-2019答案.docx

    快速排序最坏时间复杂度为O(n²),最好时间复杂度为O(nlog2n),平均时间复杂度为O(nlog2n),空间复杂度为O(log2n),排序算法不稳定 5.简单选择排序思想:设排序元素放在数组R[0....n-1]中,排序过程中,R被划分成两...

    Java容器.xmind

    copy的容器副本过大时,速度慢,不易使用 CopyOnWriteArraySet 底层使用CopyOnWriteArrayList实现 使用addIfAbsent()添加元素时,会遍历数组,如果存在元素,则抛弃副本 ConcurrentHashMap 初始容量默认为16段...

    C语言基本排序算法之shell排序实例

    本文实例讲述了C语言基本排序算法之shell排序。分享给大家供大家参考,具体如下: shell排序是对直接插入方法的改进方法. /*---------------------------------------------... 最坏运行时间为O(N^2). 最坏情形:数组

Global site tag (gtag.js) - Google Analytics