之前用了个分治法用O(n)时间复杂度简洁查找diK大数的问题。可以参考下面博客:
http://blog.csdn.net/kenden23/article/details/14645619
但是由于过于复杂,估计很多人都不想使用。
下面我用随机法来解决这个问题吧,据复杂的数学分析随机法的时间是少于4n的,而分治法反而是4n,所以其实随机法更加优化了,而且更加重要的是更加简单了。
我刚看到这个算法也是震惊了,只有分治法的不到三分之二的长度。细读一下你会发现真的是很好很强大!
下面看完整程序是如何的:
原创出处:靖空间http://blog.csdn.net/kenden23/article/details/14646479
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<time.h>
using namespace std;
//low and up have to be according indices in C++;
//k mean the kth number, according C++ stlye index is k-1
int selectKthNumRand(vector<int> &vi, int low, int up, int k)
{
int mIndex;
//注意这里会有几率是up=0, low=0,所以要作特殊处理
if(up-low != 0)
mIndex = rand()%(up-low) + low;
else mIndex = 0;
int mNum = vi[mIndex];
vector<int> vec1, vec2, vec3;
for (int i = low; i <= up; i++)
{
if(vi[i] > mNum) vec3.push_back(vi[i]);
if(vi[i] == mNum) vec2.push_back(vi[i]);
if(vi[i] < mNum) vec1.push_back(vi[i]);
}
if(vec1.size()>=k)
return selectKthNumRand(vec1, 0, vec1.size()-1, k);
else if(vec1.size()+vec2.size()>=k)
return mNum;
else if(vec1.size()+vec2.size()<k)
return selectKthNumRand(vec3, 0, vec3.size()-1, k-vec1.size()-vec2.size());
}
int main()
{
int a[] = {3,5,7,9,2,12,1,0,8,14,4,6,10,11,13,5,8,12};
vector<int> va(a, a+18);
int b[] = {31,25,37,49,52,63,71,20,87,95,34};
vector<int> vb(b, b+11);
for(auto x: va)
cout<<x<<" ";
cout<<endl;
srand(time(NULL));
int mid = selectKthNumRand(va, 0, va.size()-1, 10);
cout<<"The Kth number is: \n";
cout<<mid<<endl;
cout<<endl;
system("pause");
return 0;
}
这个程序的强大之处是它随机地选择分列的下标,而不用前面那种复杂的分治法。
时间复杂度最坏情况还是O(n*n),但是平均时间复杂度已经达到了O(n)了,非常好。
运行结果:
分享到:
相关推荐
主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下
算法-数据结构和算法-2-最坏时间复杂度和计算规则.rar
很多算法的每一个计算步骤都是固定的,而在下面我们要讨论的概率算法,允许算法在执行的过程中随机选择下一个计算步骤。许多情况下,当算法在执行过程中面临一个选择时,随机性选择常比最优选择省时。因此概率算法可...
大数据-算法-CPM低复杂度解调与同步算法的研究.pdf
算法-数据结构和算法-1-算法的引入和算法时间复杂度.rar
大数据-算法-k错线性复杂度分布研究.pdf
大数据-算法-k错线性复杂度分布研究朱凤翔.pdf
算法的时间复杂度分析 期刊网站都是要现金的哦。
关于算法时间复杂度的计算 关于算法时间复杂度的计算 关于算法时间复杂度的计算
算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典算法 时间复杂度 空间复杂度 经典
大数据-算法
算法实验代码和报告(时间复杂度、0-1背包问题、分治与贪心、蛮力法)。
分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2-OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点,将车辆路径问题(VRP)转化为多旅行商 (MTSP)问题,并通过分析 MTSP进行 2-OPT操作的...
数据结构时间复杂度
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
一个简单的大数相乘的程序,复杂度O(n平方)。
DS-CDMA中一种低复杂度的多用户检测算法pdf,DS-CDMA中一种低复杂度的多用户检测算法
- 算法的时间复杂度和空间复杂度 - 三大算法思维:贪心,二分,动态规划 - 常见数据结构 ## 注意事项 - 算法,有难度,轻耐心学习 - 不仅关注题目本身,更要关注知识点和解题思路 - 按顺序学习(本章课程按顺序...