K分位数问题实现,对一个含有n个元素的集合来说,所谓的k分位数,就是能把已排序的集合分成k个大小相等的集合的“k-1个顺序统计量”。请给出一个能求出含有n个元素(无序)的集合的k分位数的O(nlgk)时间的算法。
以下为程序代码:
public static void findKthQuantile(int[] src, int p, int r, int k){
if (k==1)return;
int med = ArrayOrder.randomSelect(src, p, r, ((r-p+1)/k)*(k/2));
System.out.println(med);
partition(src, med);
findKthQuantile(src, p, p+((r-p+1)/k)*(k/2)-1, k/2);
findKthQuantile(src, p+((r-p+1)/k)*(k/2), r, k-k/2);
}
public static void partition(int[] src, int m){
int j = 0;
int temp;
for (int i = 0; i < src.length; i++) {
if (src[i]<=m) {
temp = src[i];
src[i] = src[j];
src[j++] = temp;
}
}
}
public static int randomSelect(int[] src, int p, int r, int i) {
if (p == r) return src[p];
int q = partitionRandom(src, p, r);
//int q = partition(src, p, r);
if ((q-p+1)==i) {
return src[q];
}
else if ((q-p+1)>i) {
return randomSelect(src, p, q-1, i);
}else {
return randomSelect(src, q+1, r, i-q+p-1);
}
}
public static int partitionRandom(int[]src, int p, int r){
int i = new Random().nextInt(r-p) + p;
int temp = src[r];
src[r] = src[i];
src[i] = temp;
return partition(src, p, r);
}
分享到:
相关推荐
基于分位数半径动态K-means的分布式负荷聚类算法是一种针对电力负荷曲线聚类问题而提出的改进方法。该算法针对传统K-means聚类算法在初始值敏感和需要事先给定类数目这两个缺陷,通过结合分位数半径概念和分布式计算...
分位数是将一组数值分成相等部分的统计量,例如,第一四分位数(Q1)是将数据分为低四分之一和高四分之三的分割点,第三四分位数(Q3)则将数据分为低三分之二和高三分之一。高亮度分位数是指在绘图时,使用特殊的...
其中,k参数用于设置展示的分位数的数量,例如k=13表示展示13个分位数。conf参数用于设置置信水平,outlier.size参数用于设置异常值的大小。 绘制letter-value图可以更好地展示数据的分布情况,例如可以看到不同分...
基于神经网络分位数回归的金融风险预警 Title:基于神经网络分位数回归的金融风险预警 Description:本文研究基于神经网络分位数回归的金融风险预警,建立了我国金融预警模型,对金融系统运行情况进行预测。 Tag...
t-Digest构造算法使用一维k-means聚类的变体来生成非常紧凑的数据结构,从而可以精确估计分位数。 这种t-Digest数据结构可用于估计分位数,计算其他等级统计数据,甚至可估计相关的度量值,例如修整均值。 为此目的...
分位数函数 分布。 随机变量的为 对于0 <= p < 1 ,其中k是自由度, P^{-1}是的。安装$ npm install distributions-chisquare-quantile 要在浏览器中使用,请使用 。用法 var quantile = require ( '...
分位数函数 分布。 随机变量的为 对于0 <= p < 1 ,其中k是形状参数, lambda是分布的速率参数。 P^{-1}是的。 安装 $ npm install distributions-erlang-quantile 要在浏览器中使用,请使用 。 用法 var...
在本研究中,分位数的核估计形式为:轧(x) = ∑K((x - Ti) / h),其中K为核函数,h为窗宽。 多元正态分布是多个随机变量的联合分布为多元正态分布的情形。当一个随机变量向量的每一个分量都是正态分布且相互之间...
分位数函数 分布。 随机变量的对于满足0 <= k <= 1的任何k返回x 成立,其中F是参数r和p的负二项式分布的累积分布函数(CDF),其中r是直到实验停止的失败次数, p是成功概率。安装$ npm install distributions...
输出每组测试数据所得出的删k位数之后的最小数。 若输出的数首位是0,无须理会,0也直接输出即可。例如:024,就直接输出024,无须改成24。 输入样例 178543 4 87654321 2 123456789 1 254193 1 90249 2 0 ...
FDR逆分位数转换用于基因组扫描摘要统计数据的快速准确的获胜者诅咒调整。 PLoS Genetics正在审查该方法,对获胜者的诅咒进行简单而准确的校正就可以预测在更大的基因组扫描中发现的信号 大纲 考虑到扫描统计数据...
基于复杂网络的脑电信号分析 将时间序列中值的范围...当x(t)与x(t+k)分别属于分位数和时,连接节点和的加权弧记为,其中t = 1,2,......,T,时间差k = 1,..., 。 此类资源为用matlab实现此类效果的主函数main.m文件
Q文摘用于回答近似分位数查询的 QDigest 数据结构。 尽管统计分析(如查找前 k 个访问过的 url)通常在服务器端完成(这很有意义),但这种特殊的数据结构在客户端也非常有用。 例如,如果您想查找用户在会话期间...
t-digest构造算法使用一维k-means聚类的变体来生成非常紧凑的数据结构,从而可以精确估计分位数。 这种t-digest数据结构可用于估计分位数,计算其他等级统计数据,甚至可估计相关的度量值(例如修整均值)。 在T-...
- 实现相对复杂,需要精心设计程序以确保正确的分时控制。 - 如果扫描速度不够快,可能会出现闪烁的现象。 #### 三、实例分析 假设我们需要驱动5个数码管显示不同的数字。 - **静态驱动情况下**,每个数码管需要8...
每种分布都介绍了相关的概率函数、分布函数、密度函数和分位数,读者可以根据需要选择合适的分布类型进行实验操作。 一、实验一:抽样分布实验 实验目的: 1. 产生来自常用分布的随机数,并计算常用分布的密度...
τ分位数回归模型可以表示为: \[ Y = \beta_0(\tau) + \beta_1(\tau)X_1 + \beta_2(\tau)X_2 + ... + \beta_k(\tau)X_k \] 其中,\(\beta_0(\tau)\), \(\beta_1(\tau)\), ..., \(\beta_k(\tau)\) 是依赖于τ的...