`

找中位数相关算法

 
阅读更多
查找第 i 大元素,除了排序外,可借助快排思想,将其划分,进而分治算法,也可堆排序

借助芯片测试,分治
http://blog.csdn.net/liu1064782986/article/details/7411720
http://blog.csdn.net/atyuwen/article/details/1817600

当有奇数个芯片两两测试,必有一个落单
1. (n-1)/2, 当分组的芯片对淘汰后保留的为奇数
    1) 落单为好
          奇数个芯片中好的至少比坏的多一个,无所谓加
    2) 为坏
                                        不能加
2. 为偶数
    1) 落单为好
          好的至少等于坏的,加
    2) 落单为坏
          好的至少壁坏的多两个,无所谓加
To sum up,
    奇数时不加,偶数时加


分治算法,注意:
将一组数据划分后,对每个子集求解,复杂度O(logn),而不是,求完第一个子集后,将其解并入第二个子集求解,依此类推,类似顺序法求解数组最大值,复杂度为O(n),这根本不是分治法。
我在分析芯片测试时犯了这错,在比较两片芯片时,是先划分为 n/2组,每组独立比较,这才是分治法


1. 一个数组中位数
public static int chipTest() {
  int i = 0, j = 0;
  int[] a = copyArray(elements);
  int[] tmp = new int[a.length];
  while(a.length > 3) {
     j = 0;
     for(i = 0; i+1 < a.length; i=i+2) {
        if(a[i]== a[i+1]) {
          tmp[j] = a[i];
          j++;
        }
     }
     if(j%2 == 0 && i== a.length-1) {
         tmp[j] = a[i];
     }
     a = copyArray(tmp);
  }
  if(a.length == 3) {
     if(a[0]==a[1]) {
         return a[0];
     } else {
         return a[2];
     }
  } else  if(a.length == 2) {
     if(a[0] == a[1]) {
         return a[0];
     } else {
         return -1;
     }
  } else {
     return a[0];
  }
}



2. 两个有序数组中位数
http://www.cnblogs.com/luxiaoxun/archive/2012/09/13/2684054.html

顺序法求解, O(n)
float GetMedian(int n) {
	int _ia = 0, _ib = 0;
	int median1 = 0;
	while(_ia < n && _ib < n && _ia+_ib < n) {
		if(g_a[_ia]<g_b[_ib]) {
			median1 = g_a[_ia];
			_ia++;
		} else {
			median1 = g_b[_ib];
			_ib++;
		}
	}
	if(g_a[_ia] < g_b[_ib]) {
		return (float)(median1+g_a[_ia])/2;
	}
	else {
		return (float)(median1+g_b[_ib])/2;
	}
}


分治法, O(logn)
float GetMedian(int _ia, int _ja, int _ib, int _jb) {
	if((_ja-_ia)%2==0 && g_a[(_ia+_ja)/2]==g_b[(_ib+_jb)/2]) {
		return g_a[(_ia+_ja)/2];
	}
	if((_ja-_ia)%2==1 && g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1]==g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {
		return (float)(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1])/2;
	}
	
	if(_ja-_ia == 1) {
		return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;
	}

	if((_ja-_ia)%2==0) {
		if(g_a[(_ia+_ja)/2] < g_b[(_ib+_jb)/2]) {
			return GetMedian((_ia+_ja)/2, _ja, _ib, (_ib+_jb)/2);
		} else {
			return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2, _jb);
		}
	} else {
		if(g_a[(_ia+_ja)/2]+g_a[(_ia+_ja)/2+1] < g_b[(_ib+_jb)/2]+g_b[(_ib+_jb)/2+1]) {
			return GetMedian((_ia+_ja)/2+1, _ja, _ib, (_ib+_jb)/2);
		} else {
			return GetMedian(_ia, (_ia+_ja)/2, (_ib+_jb)/2+1, _jb);
		}	
	}
}


tips
1. 分治算法,复杂度与 logn有关,基本都是递归
2. 递归算法可能有多个终止条件,如本题
3. 当递归到最简形式,亦即某一终止条件
      两数组为  a, b
                c, d
      注意到隐含条件,每个数组有序,a<b,c<d
      所以有
return (float)(max(g_a[_ia], g_b[_ib])+min(g_b[_ja], g_b[_jb]))/2;


Error:
   没弄懂分治的精髓,在于,不断的大化小,而不是只简化一次。
   对于这题,根据两个数组的中位数比较,将规模简化到 O(n+1),就没有进一步化简,这样复杂度仍为 O(n),实际上,根据中位数性质,进一步化简后,原问题的中位数不变,所以可以进一步缩小问题规模
    而对于算法书 P48 2.17题,也是用分治,将排序规模减小,但此次减小后即不能化简,所以只能使用一次,为用到递归。
分享到:
评论

相关推荐

    线性时间选择中位数算法

    ### 线性时间选择中位数算法 #### 实验目的 1. **掌握线性时间选择的基本算法及其应用:** 线性时间选择算法是一种可以在平均或最坏情况下达到线性时间复杂度的选择算法,它主要用于在无序数组中找到第k小的元素。...

    条件中位数及其改进算法的Matlab实现_kekaoxing_matlab可靠性_条件中位数_

    通过阅读提供的“条件中位数及其改进算法的Matlab实现.docx”文档,用户不仅可以理解条件中位数的基本原理,还能学习如何在Matlab环境下编写代码实现这一方法,为实际工程问题提供统计解决方案。同时,文档可能还会...

    找出两个升序序列的中位数算法理解

    总结来说,找出两个升序序列的中位数算法关键在于利用升序排列的特性,通过分治策略和二分查找高效地定位中位数。理解这一算法不仅有助于提高编程能力,还能在实际问题解决中发挥重要作用,比如在大数据分析、排序...

    算法导论中位数和顺序统计量

    在实际应用中,中位数和顺序统计量经常被用于实时数据分析,比如监控系统性能指标,或者在数据库查询中找出前k个最大或最小的记录。此外,它们也是许多复杂算法的基础,如快速选择和快速排序。 为了实现这些功能,...

    C++算法:寻找两个有序数组的中位数

    请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] ...

    利用中位数输油管道算法的解析

    具体算法上,我们使用了一个名为 `guandao` 的函数,该函数接收油井纵坐标数组 y[] 和其长度 n,然后根据 n 是偶数还是奇数调用 `select` 函数来找出中位数。`select` 函数是一种在未排序数组中查找第 k 小元素的...

    滤波算法集合(中位数、中位数平均、平均、加权平均、一阶加权、正太分布)

    滤波算法集合(中位数、中位数平均、平均、加权平均、一阶加权、正太分布)

    算法设计与分析 中位数问题 c++程序

    本篇文章将详细探讨C++实现的中位数算法,并结合提供的压缩包文件进行解析。 中位数是指一组数值序列中处于中间位置的数,当数值个数为奇数时,中位数是正中间的那个数;若为偶数,则中位数通常取中间两个数的平均...

    时间复杂度为O(n)的找中位数算法源代码

    ### 时间复杂度为O(n)的找中位数算法 #### 一、算法背景与目标 在计算机科学中,寻找一个数组中的中位数是一种常见的需求。中位数是指将一组数值按大小顺序排列后位于中间位置的数。如果数值个数是奇数,则中位数...

    求两个等长升序序列的中位数算法实现源码

    在编程领域,中位数是数据排序后位于中间位置的数值,对于等长的升序序列,中位数的计算通常有两种情况:如果序列长度为奇数,中位数是中间那个数;如果序列长度为偶数,中位数则是中间两个数的平均值。本篇文章将...

    分治法求两列有序数组的中位数的程序

    (1)设X[0:n-1]和Y[0:n-1]为两个数组,每个数组中含有n个已排好序的数,设计一个算法复杂度为O(logn)的分治算法,找出X和Y中2n个数中的中位数。(中位数:个数为奇数:中间位置上的数;个数为偶数,中间两个数的...

    基于opencv的像中位切分算法

    首先,计算所有像素的灰度值,并找出中位数,即灰度值中间的点。然后,根据这个中位数将像素分为两部分:一部分像素的灰度值小于或等于中位数,另一部分大于中位数。接着,对每一部分重复这个过程,直到满足预设的...

    求两个序列的中位数 减治法——C++代码

    在编程领域,寻找两个有序序列的中位数是一项常见的任务,尤其在算法设计和数据分析中。这个题目要求我们使用C++编程语言来实现一个减治法(Divide and Conquer,也译为分治法)的解决方案。减治法是一种有效的算法...

    C++实现查找中位数的O(N)算法和Kmin算法

    本文实例讲述了C++实现查找中位数的O(N)算法和Kmin算法,分享给大家供大家参考。具体方法如下: 利用快速排序的partition操作来完成O(N)时间内的中位数的查找算法如下: #include #include #include #include ...

    c语言中位数

    以上就是从给定的标题和描述中提炼出的C语言中位数相关知识点。这个程序不仅涉及基本的数据存储(数组)和数据处理(排序),还包含了寻找特定统计量(中位数)的过程,同时展示了C语言项目开发中的一些辅助文件及其...

    找中位数1

    【标题】:“找中位数1”通常是指在数据处理和算法设计中寻找一组数值的中位数问题。中位数是一组数据有序排列后位于中间位置的数值,当数据量为奇数时,它是正中间的那个数;当数据量为偶数时,中位数是中间两个数...

    带权中位数查找O(n)C++

    "带权中位数查找O(n)C++"是一个关于高效算法实现的话题,它涉及到如何在一组数据中快速找到带权重的中位数,且该过程的时间复杂度仅为线性,即O(n)。下面将详细解释这个概念及其在C++中的实现。 首先,我们要明确...

    2020-算法设计与分析-期末试题1

    本文将详细讨论在2020年春季学期算法设计与分析期末考试中出现的几个关键知识点,包括欧几里德算法、阶乘的对数复杂度、递归方程、权重中位数、二分图判断、动态规划、苹果购买优化、动态多重集合数据结构、字符串...

    设计一个算法求两个有序序列的中位数.cpp

    13,15,17,19),其中位数是15,若b=(2,4,6,8,20),其中位数为6。...长有序序列的中位数是含它们所有元素的有序序列的中位数,例如a、b两 个有序序列的中位数为11。设计一个算法求给定的两个有序序列的中 位数。

Global site tag (gtag.js) - Google Analytics