`
wcdzxxgc
  • 浏览: 83570 次
  • 性别: Icon_minigender_1
  • 来自: 武汉
社区版块
存档分类
最新评论

K分位数问题

阅读更多
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);
 }

0
0
分享到:
评论

相关推荐

    基于分位数半径动态K-means的分布式负荷聚类算法.pdf

    基于分位数半径动态K-means的分布式负荷聚类算法是一种针对电力负荷曲线聚类问题而提出的改进方法。该算法针对传统K-means聚类算法在初始值敏感和需要事先给定类数目这两个缺陷,通过结合分位数半径概念和分布式计算...

    matlab开发-用高亮度分位数绘制数据的正常分布图

    分位数是将一组数值分成相等部分的统计量,例如,第一四分位数(Q1)是将数据分为低四分之一和高四分之三的分割点,第三四分位数(Q3)则将数据分为低三分之二和高三分之一。高亮度分位数是指在绘图时,使用特殊的...

    28.R语言绘图_ggplot2_更多分位数的箱线图letter-value的绘制方法汇总.pdf

    其中,k参数用于设置展示的分位数的数量,例如k=13表示展示13个分位数。conf参数用于设置置信水平,outlier.size参数用于设置异常值的大小。 绘制letter-value图可以更好地展示数据的分布情况,例如可以看到不同分...

    基于神经网络分位数回归的金融风险预警.pdf

    基于神经网络分位数回归的金融风险预警 Title:基于神经网络分位数回归的金融风险预警 Description:本文研究基于神经网络分位数回归的金融风险预警,建立了我国金融预警模型,对金融系统运行情况进行预测。 Tag...

    tdigest:使用“ t-摘要”快速,准确的分位数

    t-Digest构造算法使用一维k-means聚类的变体来生成非常紧凑的数据结构,从而可以精确估计分位数。 这种t-Digest数据结构可用于估计分位数,计算其他等级统计数据,甚至可估计相关的度量值,例如修整均值。 为此目的...

    chisquare-quantile:卡方分布分位数函数

    分位数函数 分布。 随机变量的为 对于0 &lt;= p &lt; 1 ,其中k是自由度, P^{-1}是的。安装$ npm install distributions-chisquare-quantile 要在浏览器中使用,请使用 。用法 var quantile = require ( '...

    erlang-quantile:Erlang分布分位数函数

    分位数函数 分布。 随机变量的为 对于0 &lt;= p &lt; 1 ,其中k是形状参数, lambda是分布的速率参数。 P^{-1}是的。 安装 $ npm install distributions-erlang-quantile 要在浏览器中使用,请使用 。 用法 var...

    ω-混合样本下有限个分位数估计的联合渐近分布 (2015年)

    在本研究中,分位数的核估计形式为:轧(x) = ∑K((x - Ti) / h),其中K为核函数,h为窗宽。 多元正态分布是多个随机变量的联合分布为多元正态分布的情形。当一个随机变量向量的每一个分量都是正态分布且相互之间...

    negative-binomial-quantile:负二项分布分位数函数

    分位数函数 分布。 随机变量的对于满足0 &lt;= k &lt;= 1的任何k返回x 成立,其中F是参数r和p的负二项式分布的累积分布函数(CDF),其中r是直到实验停止的失败次数, p是成功概率。安装$ npm install distributions...

    8605 删数问题

    输出每组测试数据所得出的删k位数之后的最小数。 若输出的数首位是0,无须理会,0也直接输出即可。例如:024,就直接输出024,无须改成24。 输入样例 178543 4 87654321 2 123456789 1 254193 1 90249 2 0 ...

    FIQT:FDR分位数逆变换

    FDR逆分位数转换用于基因组扫描摘要统计数据的快速准确的获胜者诅咒调整。 PLoS Genetics正在审查该方法,对获胜者的诅咒进行简单而准确的校正就可以预测在更大的基因组扫描中发现的信号 大纲 考虑到扫描统计数据...

    基于复杂网络的脑电信号分析 main.m

    基于复杂网络的脑电信号分析 将时间序列中值的范围...当x(t)与x(t+k)分别属于分位数和时,连接节点和的加权弧记为,其中t = 1,2,......,T,时间差k = 1,..., 。 此类资源为用matlab实现此类效果的主函数main.m文件

    QDigest:用于回答近似分位数查询的 QDigest 数据结构

    Q文摘用于回答近似分位数查询的 QDigest 数据结构。 尽管统计分析(如查找前 k 个访问过的 url)通常在服务器端完成(这很有意义),但这种特殊的数据结构在客户端也非常有用。 例如,如果您想查找用户在会话期间...

    t-digest:一种新的数据结构,用于精确在线累积基于等级的统计信息,例如分位数和修整后的均值

    t-digest构造算法使用一维k-means聚类的变体来生成非常紧凑的数据结构,从而可以精确估计分位数。 这种t-digest数据结构可用于估计分位数,计算其他等级统计数据,甚至可估计相关的度量值(例如修整均值)。 在T-...

    4位数码管引脚图及驱动方式

    - 实现相对复杂,需要精心设计程序以确保正确的分时控制。 - 如果扫描速度不够快,可能会出现闪烁的现象。 #### 三、实例分析 假设我们需要驱动5个数码管显示不同的数字。 - **静态驱动情况下**,每个数码管需要8...

    数理统计实验操作手册.doc

    每种分布都介绍了相关的概率函数、分布函数、密度函数和分位数,读者可以根据需要选择合适的分布类型进行实验操作。 一、实验一:抽样分布实验 实验目的: 1. 产生来自常用分布的随机数,并计算常用分布的密度...

    百分位数回归及应用研究.docx

    τ分位数回归模型可以表示为: \[ 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)\) 是依赖于τ的...

Global site tag (gtag.js) - Google Analytics