【问题描述】每次都是优化选出一个元素（分组后的中位数）为划分基准，在线性时间内寻找第i小元素。提示：分组时的组的个数为n/5的向下取整；分组后的中位数取第（num_group/2向上取整）小的元素。
【输入形式】在屏幕上输入若干整数，各数间都以一个空格分隔。再输入要寻找的元素是数组从小到大顺序中第几个位置。
【输出形式】第一次划分基准元素，和数组从小到大顺序中要寻找的那个位置的元素。
【样例1输入】
2 9 8 0 7 10 1 12 3 14 5 13 6 11 4
3
【样例1输出】
7
2
【样例1说明】
输入：15个整数，以空格分隔。要寻找第3小元素。
输出：7表示第一划分基准元素为7，2表示第3小元素为2。
2021-10-28 22:31:30
871B
1
线性时间选择
给定线性序集中n个元素和一个整数k，1≤k≤n，要求找出这n个元素中第k小的元素
template
Type RandomizedSelect(Type a[],int p,int r,int k)
{
if (p==r) return a[p];
int i=RandomizedPartition(a,p,r),
j=i-p+1;
if (k<=j) return RandomizedSelect(a,p,i,k);
else return RandomizedSelect(a,i+1,r,k-j);
}
在最坏情况下，算法randomizedSelect需要O(n2)计算时间但可以证明，算法randomizedSelect可以在O(n)平均时间内找出n个输入元素中的第k小元素。
2021-10-28 21:15:41
813KB
1
VoronoiDiagramJavaRecursive
用分治法计算二维Voronoi图
算法描述：Franco Preparata和Michael Shamos的“计算几何学简介”，1985年
Alex Shavlovsky的Java实现，2018年
2021-10-25 14:51:33
510KB
1
Gray码是一个长度为2的N次幂的序列，序列中无相同元素，每个元素都是长度为N位的（0，1）串，相邻元素恰好只有一位不同，用分置策略设计一个算法对任意的N构造相应的Gray码。
2021-10-24 15:50:48
537B
1