给定 n 个实数 ,找出这n个数在实轴上相邻两个数 的 最大差值
如输入 2.3, 3.1, 7.5, 1.5, 6.3
(注意 无序哦)
最大差值:6.3-3.1=3.2
赫赫 ,不要先想排序 !
提示:
利用 鸽笼原理 :5个数,设 6个相同大小的桶在实轴上覆盖5个数 , 则必有一桶里没有数字 ,则知道最大差值了吧 ,嘿嘿,线性算法!
代码:
/**
* Author: yiminghe
* Date: 2008-10-7
* Time: 23:14:27
* Any problem ,contact yiminghe@fudan.edu.cn.
*/
public class GapSearch {
//类内 函数内 变量初始化
private static double getMin(double[] data) {
if (data.length < 1)
throw new IllegalArgumentException("argument error");
double min = data[0];
for (int i = 1; i < data.length; i++) {
min = Math.min(min, data[i]);
}
return min;
}
private static double getMax(double[] data) {
if (data.length < 1)
throw new IllegalArgumentException("argument error");
double max = data[0];
for (int i = 1; i < data.length; i++) {
max = Math.max(max, data[i]);
}
return max;
}
private static double gap(double[] data) {
double min = getMin(data);
double max = getMax(data);
if (data.length == 2)
return max - min;
int bucket = data.length + 1;
int[] count = new int[bucket];
double[] low = new double[bucket];
double[] high = new double[bucket];
for (int i = 0; i < bucket; i++) {
low[i] = max;
high[i] = min;
}
double gapV = (max - min) / bucket;
for (int i = 0; i < data.length; i++) {
int gapC = (int) ((data[i] - min) / gapV);
gapC = (gapC == bucket) ? gapC - 1 : gapC;
count[gapC]++;
low[gapC] = Math.min(low[gapC], data[i]);
high[gapC] = Math.max(high[gapC], data[i]);
}
double left = high[0];
double maxGap = 0;
for (int i = 1; i < bucket; i++) {
if (count[i] != 0) {
System.out.println(low[i] + " - " + high[i]);
maxGap = Math.max(maxGap, low[i] - left);
left = high[i];
}
}
return maxGap;
}
public static void main(String[] args) {
double[] data = new double[]{2.3d, 3.1d, 7.5d, 1.5d, 6.3d};
System.out.println(gap(data));
}
}
分享到:
相关推荐
介绍最大间隔矩阵分解,低秩分解,以及一个快速的解决算法
支持向量机之最大间隔.pdf
基于最大间隔准则的鲁棒多流形判别局部图嵌入算法.pdf
基于最大间隔的决策树归纳算法.docx基于最大间隔的决策树归纳算法.docx基于最大间隔的决策树归纳算法.docx基于最大间隔的决策树归纳算法.docx基于最大间隔的决策树归纳算法.docx基于最大间隔的决策树归纳算法.docx...
基于马尔可夫的中文分词相关的研究,机器学习
在本文中,我们提出了一个额外的工具(ISI,MSE和BER的补充),用于基于最大时间间隔误差(MTIE)准则分析收敛区域中的均衡性能,该准则用于规范时钟稳定性要求。电信标准。 与缺少该信息的已知工具(BER,ISI,MSE...
问题描述: 最大间隙问题:给定n 个实数x1, x2 ,..., xn,求这n 个数在实轴上相邻2 个数之间的最大差值。假设对任何实数的下取整函数耗时O(1),设计解最大间隙问题的线性时间算法
实验表明,此种以最大间隔符号特征为基准点的分割算法抗干扰能力强,解决了对噪声、光照变化、污染等情况的干扰,分割准确率高且速度快,并能够通过分割基准点的特征准确地细分出武警车、警车、军车车牌的类别,分割率...
但是,通过这种方法对数据进行建模时会遇到一个问题,即当超出范围时,该方法就会失效。 这项研究提供了一种解决数据建模的方法,即使该数据包含联系也是如此。 为此,确定了一个最佳阈值,该阈值为极端事件提供了...
针对此问题,提出一种基于少量负类样本的最大间隔方法,其基本思想是:先构造一个超球面,让它包含尽可能多的正常实例,同时,球表面到正常实例之间的间隔越大越好,从而得到一个围绕正常实例的闭合而又紧贴异常实例...
为了从理论上分析不同间隔位置对爆破效果的影响,选出理论上最优的间隔位置,运用大型动力分析软件LS-DYNA对孔...最后,从峰值振速结合最大主应力进行分析,得出中部间隔降振效果最好且对爆破效果无影响,为理论上最佳方案。
为了解决上述问题, 在MEC算法的基础上引入最大中心间隔项与缩放因子η, 构造出了全新的目标函数, 称为η型最大中心间隔极大熵聚类η-MCS-MEC算法。该算法通过调控中心点间的距离使之达到最大, 并有效利用缩放因子η...
一种集成式Beta过程最大间隔一类分类方法.docx
针对当前异常检测方法面临的分类性能有限以及分类结果易受噪声影响等问题,在分析当前异常检测方法的基础上,提出模糊大间隔最小超球模型FMHM。该模型引入模糊理论,在一定程度上减少了噪声对分类结果的影响;正常...
行业分类-设备装置-基于最大间隔张量学习的高维多媒体数据分类方法.zip
针对这类问题,通过分析现有三种保护间隔的特点,提出一种保护间隔样式的识别方法。该方法定义一个时域自相关函数,利用循环前缀的自相关性构造的特征值识别出CP-OFDM。由单个符号幅度的平方值构造功率自相关函数,...
针对不平衡样本下的故障检测,不平衡样本下具有很好的优越性
毕业设计 最大间隔聚类MMC和多核聚类MKC源码+详细文档+全部数据资料 高分项目.zip毕业设计 最大间隔聚类MMC和多核聚类MKC源码+详细文档+全部数据资料 高分项目.zip 【备注】 1、该项目是高分毕业设计项目源码,已获...
音视频-编解码-最大间隔方法及其在图像检索中.pdf
提出了基于最优超平面与支持向量机思想的最大间隔聚类算法。该方法借鉴了最优超平面思想和用核函数非线性映射构造支持向量机的思想。通过构造一个二次规划问题,得到了使分类后两类间距最大的聚类方法,并且借助非线性...