求第i个小的元素 时间复杂度O(n)
2024-10-18 20:24:57
#include<iostream> //求第i个小的元素 时间复杂度O(n)
#include<cstdlib>
#include<ctime>
using namespace std; void swap(double *dPara1, double *dPara2)
{
double temp = 0.0;
temp = *dPara1;
*dPara1 = *dPara2;
*dPara2 = temp;
} int randompartitionA( double dArr[], int p, int q) //划分
{
srand((unsigned)time(NULL));
int account = q-p+1;
int index = 0;
int i = p;
index = rand()%account+p;
swap(dArr[p], dArr[index]);
int x = dArr[p];
for( int j=p+1; j<=q; j++)
{
if( dArr[j]<=x )
{
i++;
swap(dArr[i], dArr[j]);
}
}
swap(dArr[i], dArr[p]);
return i;
} int randompartitionB( double dArr[], int p, int q) //划分
{
srand((unsigned)time(NULL));
int account = q-p+1;
int index = 0; index = rand()%account+p;
swap(dArr[p], dArr[index]);
double x = dArr[p]; int low = p;
int high = q; while( low<high )
{
while(low<high&&x<dArr[high]) --high;
dArr[low]=dArr[high];
while(low<high&&x>dArr[low]) ++low;
dArr[high]=dArr[low];
}
dArr[low] = x;
return low;
} double RANDOMIZED_SELECT( double dArr[], int p, int q, int i)
{
if( p==q )
{
return dArr[p];
}
int r = randompartitionB( dArr, p, q); // int r = randompartition( dArr, p, q);
int k = r-p+1;
if( i==k )
{
return dArr[r];
}
else if( i<k )
{
return RANDOMIZED_SELECT( dArr, p, r-1, i);
}
else
{
return RANDOMIZED_SELECT( dArr, r+1, q, i-k);
}
}
int main()
{
double darr[9] = { 1.0, 2.0 ,6.3, 3.5, 8.3, 0.43, 9, 10, 2.2 };
cout<<RANDOMIZED_SELECT( darr, 0, 8, 5);
cout<<endl;
return 0; }
最新文章
- SharePoint 2013 Designer系列之自定义列表表单
- delphi控件安装与删除
- 解决 Cocos2d-x 中 Android.mk 手动添加源文件
- Hex-Rays decompiler type definitions and convenience macros
- json字符串转换为JSONObject和JSONArray
- KMP算法总结
- Android Service 启动和停止服务
- ajax+struts2 实现省份-城市-地区三级联动
- Python 数据结构和算法
- hibernate 的第一个工程
- Java基础——Ajax(三)
- sklearn模块函数介绍
- CSS魔法(二)
- iOS 开发笔记-获取某个APP素材
- Row_number 详解
- POJ-3414.Pots.(BFS + 路径打印)
- Promise.all函数的使用
- HDU 1262 寻找素数对 模拟题
- python 调试方法
- OTL使用指南
热门文章
- 使用linq对字符串1,2,3,4,5,6,7,8,9,10求和
- 【Cocos2d-x游戏引擎开发笔记(25)】XML解析
- javascript 剔除数组中相同的值,合并数组中相同项
- 解决Xcode 7编译错误:does not contain bitcode
- os内存使用管理之unix-AIX篇
- 8天玩转并行开发——第二天 Task的使用
- 微信5.0 Android版飞机大战破解无敌模式手记
- Swift - 使用下划线(_)来分隔数值中的数字
- mssql 返回表的创建语句
- 基于visual Studio2013解决面试题之0201二叉树转链表