找出一个组元素中的中位数(中间值,它不大于一半的元素也不小于另一半的元素),是一个和排序有关但又不需要完全排序的重要应用。查找中位数在统计和许多数据处理中很常见。
可以把查找中位数看成是一种特殊的选择:在数组中查找第k个小或大的元素。我们可以回想前面《快速排序及改进》中的partition(Comparable[] a,int lo,int hi)方法,它会将数组的a[lo]到a[hi]重新排列(局部排序)并返回一个整数j,使得:
a[lo ... j - 1] <= a[j] <= a[j + 1 ... hi]
那么,要获取第K小的值,当k = j时,a[j]就是要求解的数值了。
/**
*查找一个数组中的第k小的元素
*/
public static Comparable select(Comparable[] a,int k){
//对数组a洗牌
shuffle(a);
int lo = 0;
int hi = a.length - 1;
int j = 0;
while(hi > lo){
j = partition(a,lo,hi - 1);
if(j == k){
return a[k];
}else if(j > k){
hi = j - 1;
}else{
lo = j + 1;
}
}
return a[k];
}
对于查找中位数,就是k = N/2时的a[j],a[j]就是要求的中位数。整个代码如下:
/**
* 取中位数
*/
public class MedianFinder extends SortBase{
/**
* 局部排序,查找数组a的中位数
* @param a
* @return
*/
public static Comparable find(Comparable[] a){
int len = a.length;
int mid = 0;
if((isOdd(len)){//奇数
mid = (len + 1)/2;
}else{
mid = len/2;
}
return select(a,mid - 1);
}
/**
* 判断整数i是否是奇数
* @param i
* @return true:奇数,false:偶数
*/
private static isOdd(int i){
return (k & 1) != 0;
}
/**
* 查找数组a中第k小的元素
* @param a
* @param k
* @return
*/
public static Comparable select(Comparable[] a,int k){
shuffle(a);
Comparable val = null;
int lo = 0;
int hi = a.length - 1;
int j = 0;
while(hi > lo){
j = partition(a,lo,hi);
if(j == k){
val = a[k];
break;
}else if(j > k){
hi = j - 1;
}else{
lo = j + 1;
}
}
return val;
}
/**
* 在数组a的下标lo和hi范围内获取快速切分的基数的小标,使该基数的左边的
* 元素都不大于该数,而右边的元素都不小于该数
* @param a
* @param lo
* @param hi
* @return 快速切分基数的下标
*/
public static int partition(Comparable[] a,int lo,int hi){
//将数组切分为a[lo...i - 1],a[i],a[j + 1,hi]
int i = lo,j = hi + 1; //设置左右扫描指针
Comparable v = a[lo]; //切分元素
while(true){
while(less(a[++i],v)){
if(i == hi) break;
}
while(less(v,a[--j])){
if(j == lo) break;
}
if(i >= j){
break;
}
exch(a,i,j);
}
exch(a,lo,j); //将v = a[i]放入正确的位置
//a[lo...j - 1] <= a[j] <= a[j + 1 ... hi]
return j;
}
}
分享到:
相关推荐
总结来说,找出两个升序序列的中位数算法关键在于利用升序排列的特性,通过分治策略和二分查找高效地定位中位数。理解这一算法不仅有助于提高编程能力,还能在实际问题解决中发挥重要作用,比如在大数据分析、排序...
本篇文章将详细探讨C++实现的中位数算法,并结合提供的压缩包文件进行解析。 中位数是指一组数值序列中处于中间位置的数,当数值个数为奇数时,中位数是正中间的那个数;若为偶数,则中位数通常取中间两个数的平均...
本篇文章将详细探讨如何实现求解两个等长升序序列中位数的算法,并提供源码实现。 首先,我们需要理解算法的基本思想。由于两个序列都是升序排列的,我们可以同时从两个序列的首元素开始比较,较小的元素进入结果...
而在带权的情况下,每个数都有一个对应的权重,中位数不再仅仅取决于数值,还要考虑权重的大小。带权中位数是所有数的权重总和中处于中间位置的那个数或其权重的累积和。 寻找带权中位数的一个常见方法是使用“权重...
如果是偶数,则中位数通常取中间两个数的平均值。这个题目涉及到的核心知识点包括数组操作、排序算法以及中位数的计算。 1. **数组操作**:数组是C语言中存储一系列同类型元素的基本数据结构。在这个小程序中,我们...
如果是偶数,则中位数通常取中间两个数的平均值。本篇文章将详细介绍如何在C/C++中计算数组的中位数。 首先,我们需要了解几种基本的数据结构和算法,它们对于求解中位数至关重要: 1. **排序**:在C/C++中,可以...
### 分治法求解两个有序数组的中位数 #### 分治法简介 分治法是一种重要的算法设计思想,其核心在于将一个复杂的问题分解成若干个规模较小但结构相似的子问题,然后递归地解决这些子问题,并将各个子问题的解组合...
### 取数对弈(算法) #### 游戏规则与背景 取数对弈是一种两人博弈的游戏,游戏的设定非常简单但蕴含了丰富的算法思想。游戏初始时,n 个整数按照一定的顺序从左至右排成一行,两位玩家(假设为甲乙双方)轮流在...
对于两个等长的有序序列,我们可以直接取它们中间位置的数作为中位数,如果序列长度为奇数,则中位数是中间的那个数;如果序列长度为偶数,则中位数是中间两个数的平均值。 接下来,我们看如何用C++实现这个算法。...
MD5(Message-Digest Algorithm 5)是一种广泛使用的哈希函数,它能够将任意长度的信息映射为固定长度的输出,通常是一个128位的二进制数,以32位十六进制数的形式表示。在本场景中,MD5被应用于创建一个基于时间的...
此外,中位数算法的性能还取决于数据类型和硬件架构,因此可能需要针对特定平台进行优化。 最后,快速查找中位数在实际应用中的表现还需要经过详细的基准测试和性能分析。在多种不同场景和数据集上的测试可以帮助...
Java 计算中位数是数据分析和统计学中非常重要的一个概念,中位数是指数据排列后,中间那个数,如果一个集合是奇数个,那么中位数就是按大小排列后,最中间那个数,如果一个集合是偶数个,那么中位数就是按大小排列...
标题中的"Middle C_中位数"指的是编程中计算中位...通过对"middle num.txt"的分析,我们可以了解具体的实现细节,包括数据输入方式、排序算法、计算中位数的逻辑等,这对于学习和理解中位数计算的C语言实现非常有帮助。
// 或者rightMedian,取决于中位数在哪一侧 } } ``` 为了使用这个分治法,我们需要一个主函数来初始化数组并调用上述的分治函数: ```cpp int main() { int nums[] = {1, 2, 3, 4, 5}; int numsSize = sizeof...
10. **代码实现**:在易语言中实现4位特定组合算法,通常会涉及到“整型变量”、“循环结构”和“位运算”等核心概念,程序员需要编写代码来生成和处理这些4位的组合。 综上所述,4位特定组合算法涵盖了许多计算机...
二次取中是指先将元素分为若干组,每组取中位数,然后再对这些中位数进行一次取中,得到的元素作为划分基准,以此来尽可能地平衡划分后的两个子数组。 算法设计过程如下: 1. 首先,将元素分组,每组r个元素。 2. ...
《算法设计与分析报告1——线性时间选择与带权中位数算法》 报告主要探讨了如何在最坏情况下以线性时间复杂度O(n)找到一组互不相同元素的带权中位数。这个问题与线性时间选择问题相似,都需要在不进行全局排序的...
这是因为在常规的中位数定义中,偶数长度列表的中位数不存在,但通常取中间两个数的较小者作为中位数。 在执行归并操作的过程中,需要特别注意的点是,一旦一个列表的元素全部被归并完毕,那么剩下的另一个列表的...
总之,“算术加中位值”滤波是数据滤波的一种混合策略,结合了算术平均滤波的平滑特性和中位数滤波的抗干扰能力,以达到更好的滤波效果。通过C++实现这样的滤波算法,可以有效地处理各种噪声和异常值,从而提供更...
本话题关注的是如何计算一个包含10个无符号整数的数组的中位数。中位数是一组数据集中间位置的数值,将数据分为相等的两部分,一半的值大于它,另一半小于或等于它。对于10个元素的数组,中位数是第5个元素,因为它...