寻找一个序列中第k小的元素——分治法
寻找一个序列中第k小的元素——分治法
#include
/*
分治策略
假设无序序列存放在a[0...n-1]中，若将a递增排序，则第k小的元素为a[k-1]。采用类似快速排序的思想
对于无序序列a[s...t]，在其中查找第k小的元素的过程
1.若s>=t，即其中只有一个元素或没有任何元素，如果s=t且s=k-1，表示只有一个元素且a[k-1]就是要求的
结果，返回a[k-1]
2.若s
子序列，基准a[i]已归位，a[s...i-1]中的所有元素均小于a[i]，a[i+1...t]中的所有元素均大于a[i]，
也就是说a[i]是第i+1小的元素，有3个情况
(1)若k-1=i，a[i]即为所求，返回a[i]
(2)若k-1
(3)若k-1>i，第k小的元素应在a[i+1...t]子序列中，递归在该子序列中求解并返回其结果
*/
int QuickSelect(int a[], int s, int t, int k);//在a[s...t]中找第k小的元素
int main()
{
int n = 10, k;
int e;
int a[] = {2, 5, 1, 7, 10, 6, 9, 4, 3, 8};
for(k = 1; k <= n; k++)
{
e = QuickSelect(a, 0, n-1, k);
printf("第%d小的元素：%d\n", k, e);
}
return 0;
}
int QuickSelect(int a[], int s, int t, int k) {
int i = s, j = t;
int tmp;
if(s < t)
{
tmp = a[s];
while(i != j)
{
while(j > i && a[j] >= tmp)
j--;
a[i] = a[j];
while(i < j && a[i] <= tmp)
i++;
a[j] = a[i];
}
a[i] = tmp;
if(k-1 == i)
return a[i];
else if(k-1 < i)
return QuickSelect(a, s, i-1, k);
else
return QuickSelect(a, i+1, t, k);
}
else if(s == t && s == k-1)
return a[k-1];
}
寻找一个序列中第k小的元素——分治法相关教程
-10-27
-10-27 创建一个登录页面 htmlhead title登录页面/title %--引入css文件和js文件--% link rel=stylesheet href=css/bootstrap.css script src=js/jquery.min.js/script script src=js/bootstrap.js/script script src=js/bootstrap.bundle.js/script styl
postman同时上传 对象(完整的json格式，而不是一个一个的参数)
postman同时上传 对象(完整的json格式，而不是一个一个的参数)与文件，附图 一：headers 设置Content-Type mutipart/form-data 二：body 传参 三：代码 public R save(@RequestParam(value=entity,required = true) String entity,@RequestParam(value=mult
Flink做一个批处理
Flink做一个批处理 用Flink做出来的第一个程序 flink初学者，第一个Wordcount其实琢磨了很久很久，但是今天终于成功了，写下来供大家参考： 打开IDEA，创建一个maven项目 命名 首先配置以下依赖：pom.xml dependencies dependency groupIdorg.apache.flink/gr
环形链表Ⅰ+Ⅱ
环形链表Ⅰ+Ⅱ 环形链表Ⅰ 题目 ：给定一个链表，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 po
Hbase中基于现有的scan对象，创建一个新的Scan对象时的注意事项
Hbase中基于现有的scan对象，创建一个新的Scan对象时的注意事项 1. 观察Scan类中的familyMap是否为深拷贝 String cf = f; Scan scan = new Scan().withStartRow(100.getBytes()).withStopRow(200.getBytes()); scan.addColumn(cf.getBytes(), col-01.getBytes
如何创建运行一个Pipeline Project
如何创建运行一个Pipeline Project Pipeline是一个流程，这个流程定义了完成过一个CI/CD流程的步骤，通过执行这个流程代替手工自动去完成CI/CD，这个流程是由使用者自己定义的。本文的目的是以最简单的方式构建一个pipline的project 用.netCore构建一个最简单
链表系列--反转链表
链表系列--反转链表 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。 示例: 输入: 1-2-3-4-5-NULL 输出: 5-4-3-2-1-NULL 解题思路 1.非法性检测。2.创建空指针，然后遍历链表，保存后面的链表的值，这样改变了链表指向后还能找到
7天带你搞定一个图表框架echarts(五)
7天带你搞定一个图表框架echarts(五) 今天整理了echarts中仪表盘，话不多说。还是通过具体案例来讲解一下仪表盘的具体配置项， var myChart = echarts.init(document.getElementById('main')); var option = { //提示框组件 //formatter表示提示框组件的显
