精华内容
下载资源
问答
  • 不排序求中位数

    千次阅读 2014-02-22 10:10:38
    不排序求中位数 /* 一组数的中位数,就是把一组数从小到大排好后位居中间的 那一个;如果有奇数个数,那么中位数就是中间的那个;如果 有偶数个数,那么中位数就是中间两个数的平均数。 那么有没有办法不用排序就...

    不排序求中位数

    /*
    一组数的中位数,就是把一组数从小到大排好后位居中间的
    那一个;如果有奇数个数,那么中位数就是中间的那个;如果
    有偶数个数,那么中位数就是中间两个数的平均数。
    那么有没有办法不用排序就可以求出中位数的方法呢?
    可以回想一下qsort中partition的作用:找出一个分界点,左边的
    数都小于分界点值,右边的数都大于分界点值。所以,只要不断地
    进行partition,直到分界点是left与right的中央元素就行了。需要
    注意的是,还要考虑到有奇数个还是偶数个数的问题。
    */
    #include<cstdio>
    
    using namespace std;
    
    void swap(int *a,int *b)
    {
    	int t=*a;
    	*a=*b;
    	*b=t;
    }
    
    void partition(int A[],int left,int right,int *pos)
    {
    	int data=A[left];
    	int i;
    	for(*pos=left,i=left+1;i<=right;i++)
    	{
    		if(A[i]<data)
    		{
    			(*pos)++;
    			swap(&A[*pos],&A[i]);
    		}
    	}
    	swap(&A[left],&A[*pos]);
    }
    
    int Getmid(int A[],int n)
    {
    	int left=0;
    	int right=n-1;
    	int mid=(left+right)/2;
    	int pos,count=1;
    	while(1)
    	{
    		partition(A,left,right,&pos);
    		if(pos==mid)
    			break;
    		else if(pos>mid)
    			right=pos-1;
    		else
    			left=pos+1; 
    		//1th  pos=3   1 5 3 7 11 9
    		//2th  pos=0   1 5 3 7 11 9
    		//3th  pos=2   1 3 5 7 11 9
    	}
    	return (n&0x1)!=0?A[mid]:(A[mid]+A[mid+1])/2;
    }
    
    int main(int argc,char *argv[])
    {
    	int Array[]={7,5,3,1,11,9};
    	int mid;
    	mid=Getmid(Array,sizeof(Array)/sizeof(int));
    	printf("The mid number of the array is: %d\n",mid);
    
    	return 0;
    }
    


    展开全文
  • 先理解快速排序。 int partition(int L[],int low,int high) { int i,num=low; for(i=low+1;i<=high;i++) { if(L[i]<L[low]) { swap(&L[i],&L[num+1]); num++; } } swap(&L...

          先理解快速排序。

    int partition(int L[],int low,int high)
    {
    	int i,num=low;
    	for(i=low+1;i<=high;i++)
    	{
    		if(L[i]<L[low])
    		{
    			swap(&L[i],&L[num+1]);
    			num++;
    		}
    	}
    	swap(&L[low],&L[num]);
    	return num;
    }

          以上面的算法代码为例,L为要排序的数组,low和high是序列的两头元素的坐标,将序列第一个元素作为哨兵,定义变量num=low,这个变量表示哨兵的最终位置。以low=0,high=L.length-1为例,即对整个数组进行第一次排序:哨兵与数组中其他所有数字进行比较,如果比哨兵小,则将该数与num+1位置的数交换,确保num+1位置的数都比哨兵小,num++。遍历完整个数组之后,num位置之前的数都比哨兵小,则num就是哨兵的最终位置,也就是说哨兵是数组中第num小的数。

    void Qsort(int L[],int low,int high)
    {
    	if(low<high)
    	{
    		int pivot=partition(L,low,high);
    		Qsort(L,low,pivot-1);
    		Qsort(L,pivot+1,high);
    	}
    }

          上面是对整个数组不断做划分,进行排序的递归算法代码。if(low<high)是保证划分的序列最少有两个数,语句中,先对整个数组进行第一次排序,得到第一个哨兵的最终位置,以此位置作为分割点,对左右两个序列进行排序,得到他们的哨兵的最终位置,再以此为分割点······最后得到有序的数组。这是快速排序的基本思路。

    -------------------------------------------------------------------------------------------------------------------------

          中位数是指一段序列中,比它大的数和比它小的数的数量相等的那个数。序列经过排序后中位数在最中间。可以联想到使用快速排序的思想,找到最终位置在n/2的那个数。

          而找中位数,是要找到最终位置在中间的那个数,即mid=(low+high)/2时的那个数。找中位数并不需要像快速排序那样找到每个数的最终位置,所以并不需要划分序列。如果进行一次partition(L,low,high)排序后找到那个数的最终位置偏右,即他的最终位置大于mid,则这个数比中位数大,又因为这个数右边的数都比这个数大,则可以high=pos-1,将这个数右边的数都舍去再进行快排。同理,如果最终位置偏左,则继续进行low=pos+1,将小于中位数的数舍去再进行快排。最后当mid=(low+high)/2时,函数结束,输出结果。

    void getmid(int L[],int low,int high)
    {
    	int mid=(low+high)/2;
    	while(1)
    	{
    		int pos=partition(L,low,high);
    		if(pos==mid)
    			break;
    		else if(pos>mid)
    			high=pos-1;
    		else low=pos+1;
    	}
    	printf("%d",L[mid]);
    }

          还有一个小问题就是数组的长度是偶数时,要输出中间两个数的平均值。可以将mid的值返回到主函数中,输出mid位置和mid+1位置的两个数的平均值即可。

    展开全文
  • 然后如果有偶数个的话,中位数就是最中间两个数的平均数 lookup lookup是根据map中的键来取出相应的值的, 如上面的 sorted.lookup(1) ,得到的结果是一个序列 Seq[Int] 如果sorted是 RDD(( 1 ,...
    val rdd=sc.makeRDD(Array(1,8,6,4,9,3,76,4))
    val sorted = rdd.sortBy(identity).zipWithIndex().map {
      case (v, idx) => (idx, v)
    }
    
    val count = sorted.count() 
    val median: Double = if (count % 2 == 0) {
      val l = count / 2 - 1
      val r = l + 1
      (sorted.lookup(l).head + sorted.lookup(r).head).toDouble / 2
    
    } else sorted.lookup(count / 2).head.toDouble
    println(median)

    首先根据元素排序(sortBy),得到有序RDD

    RDD[Int]=(1,3,4,4,6,8,9,76)

    WithIndex后与index调换顺序.

    (1,1),(2,3),(3,4),(4,4),(5,6),(6,8),(7,9),(8,76)

    然后如果有偶数个的话,中位数就是最中间两个数的平均数

    lookup

    lookup是根据map中的键来取出相应的值的,
    如上面的sorted.lookup(1) ,得到的结果是一个序列Seq[Int]
    如果sorted是

    RDD((1,(1"a",1.0)),(1,(2,"b",9.1))

    sorted.lookup(1)得到的就是Seq[(Int,String,Double)],是键为1的所有值的序列,

    println(sorted.lookup(1))
    //是
    WrappedArray((1,a,1.0),(2,b,9.0))
    sorted.lookup(1).head是第一项,即(1,a,1.0),
    sorted.lookup(1).tail是第二项,即Seq[(Int,String,Double)]
    展开全文
  • 程序设计-N个数的中位数(C++)

    万次阅读 2019-02-28 10:19:02
    * n个数的中位数 - C++ - by Chimomo * * 对于一组有有限个数的数据来说,它们的中位数是这样的一种数:这群数据里的一半的数据比它大,而另外一半数据比它小。 * 计算有限个数的数据的中位数的方法是:把所有...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net

    /*
     * 求n个数的中位数 - C++ - by Chimomo
     *
     * 对于一组有有限个数的数据来说,它们的中位数是这样的一种数:
     * 这群数据里的一半的数据比它大,而另外一半数据比它小。
     *
     * 计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。
     * 如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;
     * 如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数。
     */
    
    #include <iostream>
    #include <cassert>
    #include <stack>
    #include <math.h>
    
    using namespace std;
    
    int QuickSortOnce(int a[], int low, int high) {
    
        // 将首元素作为枢轴。
        int pivot = a[low];
        int i = low, j = high;
    
        while (i < j) {
    
            // 从右到左,寻找首个小于pivot的元素。
            while (a[j] >= pivot && i < j) {
                j--;
            }
    
            // 执行到此,j已指向从右端起首个小于或等于pivot的元素。
            // 执行替换。
            a[i] = a[j];
    
            // 从左到右,寻找首个大于pivot的元素。
            while (a[i] <= pivot && i < j) {
                i++;
            }
    
            // 执行到此,i已指向从左端起首个大于或等于pivot的元素。
            // 执行替换。
            a[j] = a[i];
        }
    
        // 退出while循环,执行至此,必定是i=j的情况。
        // i(或j)指向的即是枢轴的位置,定位该趟排序的枢轴并将该位置返回。
        a[i] = pivot;
    
        return i;
    }
    
    void QuickSort(int a[], int low, int high) {
        if (low >= high) {
            return;
        }
    
        int pivot = QuickSortOnce(a, low, high);
    
        // 对枢轴的左端进行排序。
        QuickSort(a, low, pivot - 1);
    
        // 对枢轴的右端进行排序。
        QuickSort(a, pivot + 1, high);
    }
    
    int EvaluateMedian(int a[], int n) {
        QuickSort(a, 0, n - 1);
    
        if (n % 2 != 0) {
            return a[n / 2];
        } else {
            return (a[n / 2] + a[n / 2 - 1]) / 2;
        }
    }
    
    int main() {
        int a[9] = {-5, 345, 88, 203, 554, 1, 89, 909, 1001};
        cout << EvaluateMedian(a, 9) << endl;
        return 0;
    }
    
    // Output:
    /*
    203
    
    */
    展开全文
  • 排序:动态数组求中位数

    千次阅读 2016-04-10 00:43:34
    题目描述输入一组整数a1, a2, …, an ,每输入一个整数,输出到此时为止的中位数中位数定义:如果数串的大小是偶数 2j,中位数是从小到大排列的第 j 个数;如果数串的大小是奇数 2j+1,中位数是从小到大排列的第 ...
  • // 利用随机化快速排序求带权中位数.cpp : Defines the entry point for the console application. // //中位数:n个元素集合中,第n/2小的元素,如果是偶数个,则选择中间二个的算术平均值。 //带权中位数:对于...
  • 无序数组中位数,数组排序时间复杂度O(N)算法 排序知识回顾
  • Arithmetic problem | 两个排序数组的中位数

    千次阅读 多人点赞 2016-07-26 08:44:43
    题目如下: 两个排序的数组A和B分别含有m和n个数,找到两个排序数组的中位数,要求时间复杂度应为O(log (m+n))。 ...【注意,下述所说的中位数是思维上面的中位数位置,并是真正的数组中位数
  • lintcode两个排序数组的中位数

    千次阅读 2017-08-31 18:41:27
    两个排序数组的中位数   描述 笔记  数据  评测 两个排序的数组A和B分别含有m和n个数,找到两个排序数组的中位数,要求时间复杂度应为O(log (m+n))。 您在真实的面试中是否遇到过...
  • O(n)的时间复杂度求中位数

    千次阅读 2020-09-26 14:45:14
    在开始O(n)时间复杂度求中位数之前,先手写一下快速排序。 快速排序的实现 Reference: 快速排序|菜鸟教程 白话经典算法系列之六 快速排序 快速搞定 快速排序的原理 如果想正序排序一个序列: 从序列中找到一个 ...
  • 排序数组中位数

    千次阅读 2011-04-10 20:19:00
    给出一个数组X和Y中所有2n个元素的中位数的O(lgn)时间的算法分析与解答: 若中位数位于X中,不妨设为X[k],即在X中有k个元素小于等于中位数,n-k个元素大于等于中位数。由于X[k]为合并后的2n个元素的中位数,则...
  • 利用SQL求中位数(已修复BUG)

    万次阅读 热门讨论 2019-09-18 16:48:36
    中位数是指将集合中的元素按照升序排序后恰好位于正中间的元素。如果元素个数是偶数,则取中间两个元素的平均值作为中位数。 那么如何利用SQL求中位数呢? 将集合的元素按照大小分为上半部分和下半部分两个子集...
  • 用快速排序中位数

    千次阅读 2013-12-20 10:39:03
    剪枝方法就是递归的时候对可能有中位数的区间就直接减掉, 这个可是很大的一个剪枝, 效率急速上升 #include #include #include using namespace std; const int mmax = 10000001; int a
  • USTCOJ 1359 查找中位数 不用排序

    千次阅读 2013-03-22 16:34:02
    该题要求读入n个整数,然后输出...当输入的数是个数是是偶数的时候,两个中位数的平均值,然后下取整输出。 一般来说,我们可以将这些数存在数组当中,然后对数组进行排序,最后利用数组下标查找即可。但也可以
  • 两个或多个已排序数组的中位数

    千次阅读 2014-03-17 20:38:36
    转自:... 一道典型的面试题 ...有两个数组,均已经按升序排列好,编程序计算这两个数组的中位数  要求:要求时间复杂度O(lgn) 空间复杂度O(1)  例子:  数组A:{1,4,6,7,9} B{2,3,5,8} 两
  • 请找出两个排序数组的中位数并且总的运行时间复杂度为 O(log (m+n)) 。 示例 1: nums1 = [1, 3] nums2 = [2] 中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 中位数是 (2 + 3)/2 = 2.5 这是问题,我刚...
  • 查找中位数(java 快速排序

    千次阅读 2016-10-31 16:14:39
    对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。 java代码:import java.util.*; /** * @version 1.0 * @author ...
  • 快速排序和寻找中位数复杂度分析

    千次阅读 2019-02-20 09:45:10
    之所以,起“快速排序和寻找中位数”这个题目,并是因为寻找中位数的时候使用了快速排序,而是这两个算法使用了一个同一个预处理结构 —— 划分,然后都是递归解决!中位数的也是根据一个数把原来的数划分一下,...
  • 给一个无序数组array和数组长度n,找出其中的中位数(这里考虑n为奇数) Sample: ***** Input: ***** @[@(500),@(120),@(7),@(220),@(3),@(8),@(4),@(200),@(100) ***** Output: ***** 100 解法一:将数组...
  • 两个排序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。 你可以假设 nums1 和 nums2 同时为空。 示例 1:...
  • ar1[]和ar2[]的中位数 可以借鉴归并排序的思想 实质上就是将将两个已经排好序的数组 合并成一个数组 的过程只是在这个过程中添加了一个计算从小到大的次序的数 (count ) 当count =n 和n+1时记录下这两个数 然后...
  • 二、输入10个整数(通过指针引用数组),实现三个函数,分别这10个整数的平均值、中位数、中值(数组名作为函数参数、通过指针引用数组),最后实现一个平均值、中位数、中值的通用函数(指向函数的指针),要求...
  • 无序数组中求中位数

    千次阅读 2017-06-08 16:34:15
    题目现有一些随机生成的数字要将其依次传入,请设计一个高效算法,对于每次传入一个数字后,算出当前所有传入数字的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字,n为已传入数字个数)。 给定一个int数组A...
  •  开始我想把两个数组X与Y放入到一个数组Z中,对Z进行排序,这样Z的中位数。但是有2点原因使得这种做法可行,1.是将2数组放入到1个数组中的过程会产生O(n)的时间,所以满足题意。2如果对新数组Z排序
  • 两个排序数组的中位数

    千次阅读 2012-09-01 16:08:35
    两个排序数组中位数,这道题是很有意思的一道题目,算法导论中9.3-8题,这题必须在O(logn)的时间复杂度求解,否则肯定悲剧。。。 这题有个关键的条件,那就是这两个数组长度相等 思路如下: 数组A:1, 3, 5, 7,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 425,590
精华内容 170,236
关键字:

不排序求中位数