C++算法导论第九章O(n)期望选择序列第i小的数字
2024-10-08 10:24:28
#include<iostream>
#include<vector>
#include<algorithm>
#include<time.h>
using namespace std;
int randomized_partition(vector<int>& vec, int le, int ri)
{
if (le == ri)
{
return le;
}
srand(time(NULL));
int _rand = le + rand() % (ri - le);
int X = vec[_rand]; //基准数
int i = le - 1, j = le;
swap(vec[_rand], vec[ri]);
while (j < ri)
{
if (vec[j] < X)
{
++i;
swap(vec[i], vec[j]);
}
++j;
}
swap(vec[i + 1], vec[j]);
return i + 1;
}
int randomized_select(vector<int>& vec, int le, int ri, int i)
//选择[le,ri]中第i小的元素,O(n)时间期望，i不是索引值
{
if (le == ri)
{
return vec[le];
}
int mi = randomized_partition(vec, le, ri);
int interval = mi - le + 1;
if (i < interval)
{
return randomized_select(vec, le, mi - 1, i);
}
else
{
if (i == interval)
{
return vec[mi];
}
else
{
return randomized_select(vec, mi + 1, ri, i - interval);
}
}
}
int main()
{
srand(time(NULL));
vector<int>vec(100);
for (int i = 0; i < 100; ++i)
{
vec[i] = rand() % 100;
}
cout << randomized_select(vec, 0, 99, 6) << endl;
sort(vec.begin(), vec.end());
for (int i = 0; i < 100; ++i)
{
cout << vec[i] << " ";
}
system("pause");
}
最新文章
- MySQL基础之索引
- JavaScript中事件和属性有什么区别吗？或者说事件与方法有什么区别？
- HDU 2069 Coin Change（完全背包变种）
- Linux命令:修改文件权限命令chmod、chgrp、chown的区别
- 京东云、新浪微博等专家畅谈Docker未来格局：开放与竞争（下）
- Codeforces Round #363 LRU(概率 状压DP)
- jQuery里ajax的用法
- linux下svn命令大全
- Which Python memory profiler is recommended
- iTween
- Fidder 监控WCF
- Git教程(9)集中式工作方式常用的设计分支的方案
- sql标准化的后缀
- PC-hosts 的使用 [可使电脑无法正常上网]
- apache 网址重定向
- codevs 3044 矩形面积求并 （扫描线）
- 达内TTS6.0课件oop_day05
- LeetCode第[16]题(Java)：3Sum Closest 标签：Array
- method.invoke()s
- Activity简说