精华内容
下载资源
问答
  • 主要介绍了python 实现在无序数组中找到中位数方法,具有很好对参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 找出无序数组中位数的方法

    千次阅读 2020-01-13 13:10:48
    今早上在LintCode上做到了这种类型的题目,题目要求找到无序数组中位数在数组的位置,一开始想到的是利用快排的思想来做,但是由于只有十五分钟的时间,就直接用最普通的方式做了,思路是map记录位置+sort排序,水...

    今早上在LintCode上做到了这种类型的题目,题目要求找到无序数组中位数在数组的位置,一开始想到的是利用快排的思想来做,但是由于只有十五分钟的时间,就直接用最普通的方式做了,思路是map记录位置+sort排序,水过去了。
    找无序数组中位数我想着我之前逛知乎的时候遇到过,用最大堆和最小堆来做的。想了想,遇到这么多次,那就整理下方法吧。

    这里中位数的定义是数组元素个数/2

    1 直接排序找中位数

    直接利用自带的sort方法排序,然后返回数组的中间索引的值
    代码如下:

        //1.直接排序
        public static int findMediaMethod1(int[] a)
        {
            if(a.length==0) return -1;
            Arrays.sort(a);
            return a[(a.length-1)/2];
        }
    

    第一种方法太暴力了,我们只需要中位数即可,而不需要对数组中所有的元素进行处理。
    这就引申出了第二种方法:

    2 利用快排思想

    快排的基本思想是选取一个哨兵元素,然后设立两个指针left,right,分别指向左端和右端,两个指针相向运动,当左右指针都遇到了违反数组次序的元素的时候左右指针交换元素(违反数组次序是指左指针找到了大于哨兵元素的元素或右指针找到了小于哨兵元素的值),这样当左右指针相遇的时候,左边的数组元素一定小于等于哨兵元素,右边的数组元素一定大于等于哨兵元素。我们可以利用这一性质来找中位数,每次进行快排操作后记录下哨兵元素的位置,如果大于中间元素的话,则我们只需要对左边进行快排操作,当小于中间元素,我们只需要对右边进行快排操作,跟二分查找很像。
    代码如下:

        //2.利用快排原理进行排序
        public static int findMediaMethod2(int[] a)
        {
            if(a.length==0) return -1;
            //中位数位置
            int mid=(a.length-1)/2;
            //左右指针位置
            int left=0,right=a.length-1;
            //进行快排操作后哨兵元素的位置
            int qsIdx=0;
            qsIdx = quickSort(left,right,a);
            while(true)
            {
                //System.out.println("qsIdx= "+qsIdx);
                if(qsIdx==mid)
                {
                    break;
                }
                else if(qsIdx<mid) qsIdx=quickSort(qsIdx+1,right,a);
                else qsIdx=quickSort(left,qsIdx-1,a);
            }
            return a[qsIdx];
        }
        public static int quickSort(int left,int right,int[] a)
        {
            int target=a[left];
            while(left<right)
            {
                while(left<right&&a[right]>=target) right--;
                a[left]=a[right];
                while(left<right&&a[left]<=target) left++;
                a[right]=a[left];
            }
            //System.out.println("left="+left);
            a[left]=target;
            return left;
        }
    

    3 利用大小堆性质

    第三种方法我是看的牛客网上的一个回答才会的。这里附上链接:
    点击这里
    大顶堆存数组中较小部分的元素,小顶堆存数组中较大部分的元素,相当于将数组分成两半了,这样
    大顶堆的堆顶或小顶堆的堆顶就是我们找的中位数。
    如何实现呢?
    1. 当插入堆中的元素个数为偶数时,将当前元素插入大顶堆,将大顶堆的堆顶元素插入小顶堆
    2. 当插入堆中的元素个数为奇数时,将当前元素插入小顶堆,将小顶堆的堆顶元素插入大顶堆
    hhh,是不是很神奇。
    代码如下:

     //3.利用大顶堆和小顶堆性质进行排序
        public static int findMediaMethod3(int[] a)
        {
            if(a.length==0) return -1;
            Queue<Integer> minHeap = new PriorityQueue<Integer>();
            Queue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2-o1;
                }
            });
            for (int i=0;i<a.length;i++)
            {
                if(i%2==0)
                {
                    maxHeap.add(a[i]);
                    int top = maxHeap.poll();
                    minHeap.add(top);
                }
                else
                {
                    minHeap.add(a[i]);
                    int top = minHeap.poll();
                    maxHeap.add(top);
                }
            }
            return a.length%2==0? maxHeap.peek():minHeap.peek();
        }
    

    总结

    上面的三种方法,第一种肯定是不提倡的,第三种的话,因为一次操作就需要一次堆插入操作(log(m))(m表示堆中元素数目),n次操作的话就是nlog(m) ,第二种感觉的话应该是nlog(n)? 不过最官方的肯定是第三种方法。

    展开全文
  • 以下摘自百度百科:对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。 由概念可得,对于一个有小到大排序好的数据集,...

    1、概念

    以下摘自百度百科:对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。

    由概念可得,对于一个有小到大排序好的数据集,若其长度是n,n为奇数,则中位数就是n/2下标的位置。如果数据集的长度是n,n为偶数,则中位数就是n/2与n/2+1下标的位置的平均值。

    获取中位数的主要时间复杂度,由排序算法的时间复杂度决定,最快为nLog(n)。

    2、优化解法

    首先将数据集的个数分成奇数和偶数两种情况进行探讨,同时发现这两种情况有共同点,如下图所示。数据集数据长度为2n+1或2n时,我们只需要把最大n+1构建成一个新的Collection,再根据奇偶情况计算中位数即可。

    而JDK恰巧有这样的数据结构:PriorityQueue(优先队列),其通过完全二叉树实现的小顶堆,插入数据的时间复杂度为Log(n),并且堆顶是最小元素。

    Java实现如下:

    public class Math {
        /**
         * 获取中位数
         * @param arr
         * @return
         */
        public Double getMedianNum(int[] arr){
            //边界值
            if(arr == null || arr.length == 0){
                return null;
            }
    
            //考虑到arr长度为1时交由下面业务逻辑处理耗时也耗空间,此处做提前判断时间复杂度也才多O(1)
            if(arr.length == 1){
                return (double) arr[0];
            }
            
            // 默认是小顶堆,大顶堆为new PriorityQueue<>(Collections.reverseOrder())
            PriorityQueue<Integer> minPQ = new PriorityQueue<>();
            int length = arr.length;
            int k = length/2+1;
    
            for(int i = 0;i<k;i++){
                minPQ.add(arr[i]);
            }
            for(int i = k;i<length;i++){
                if(minPQ.peek() < arr[i]){
                    minPQ.poll();
                    minPQ.add(arr[i]);
                }
            }
            if (length % 2 == 0){
                return (minPQ.poll() + minPQ.peek())/ 2.0;
            } else{
                return minPQ.peek().doubleValue();
            }
        }
    }

    展开全文
  • 无序数组中位数

    千次阅读 2018-10-02 21:35:01
    无序数组中位数,我们首先想到的是将该数组进行排序,然后找到中间的元素,但是往往面试的时候,面试官就会怼你,说你时间复杂度太高了....要你优化(个人感觉,面试官对你问了问题,有一个自己的标准,如果你答...

    求无序数组的中位数,我们首先想到的是将该数组进行排序,然后找到中间的元素,但是往往面试的时候,面试官就会怼你,说你时间复杂度太高了....要你优化(个人感觉,面试官对你问了问题,有一个自己的标准,如果你答不到他的点子上,他就不满意,各种怼,直到你想到他的标准,否则,挂掉),针对上面的问题,用一下两种方法求解

     

    1 先排序后取中间值:

    注意:python 3里面的运算符:"//":取整  "/" :真除法   "~":按位取反运算符:对数据的每个二进制位取反,即把1变为0,把0变为1 。~x类似于 -x-1

    def get_middle(array):
        array.sort()
        index = len(array)//2
        return (array[index]+array[~index])/2
    
    print(get_middle([2,1,5,8,3,9,4]))
    print(get_middle([2,1,5,8,3,9,4,6]))

    2 通过构建最小堆来求解

    思想是:

    1 对无序数组的前len(array)//2长度的元素建立最小堆,这样就得到了一个堆顶元素小于任意一个堆里的元素

    2 将剩下的一半元素依次与堆顶元素比较。若比堆顶元素大,则替换之,并调整堆。(也就是说:依次遍历剩下一般的元素,与当前的堆顶元素作比较,如果大于堆顶元素,则替换,这时,重新调整堆的结构,使其保持为最小堆,否则,遍历下一个元素,知道剩下的一半元素遍历结束)

    3 数组剩下的所有元素比较完后,可以输出中位数。数组长度为奇数时,输出堆顶元素即可。数组长度为偶数时,输出堆顶元素与它的孩子结点中较小的那个的均值。

    def heap_adjust(parent,heap):   #更新结点后进行调整
        child=2*parent+1
        while len(heap)>child:
            if child+1<len(heap) and heap[child+1]<heap[child]:
                child+=1
            if heap[parent]<=heap[child]:
                break
            heap[parent],heap[child]=heap[child],heap[parent]
            parent,child=child,child*2+1
     
    def find(nums):
        k=len(nums)//2 +1
        heap=nums[:k]
        for i in range(k,-1,-1):   #前n/2个元素建堆
            heap_adjust(i,heap)
        for j in range(k,len(nums)):
            if nums[j]>heap[0]:
                heap[0]=nums[j]
                heap_adjust(0,heap)
        #奇数时是最中间的数,偶数时是最中间两数的均值
        return heap[0] if len(nums)%2==1 else float(heap[0]+min(heap[1],heap[2]))/2
     
    print(find([1,2,8,9,3,5,4,6,7,0]))
    print(find([1,3,2,4])

    展开全文
  • 无序数组中位数

    千次阅读 2018-12-07 16:34:46
    长度为 n 的无序数组,求中位数,如何尽快的估算出中位数,算法复杂度是多少? 算法 1(建立最小堆): 如果数组中元素有奇数个,可以采用这种算法: 步骤 1 :可以将数组的前 (n+1)//2 个元素,建立 1 个最小堆; ...

    长度为 n 的无序数组,求中位数,如何尽快的估算出中位数,算法复杂度是多少?

    算法 1(建立最小堆):

    如果数组中元素有奇数个,可以采用这种算法:
    步骤 1 :可以将数组的前 (n+1)//2 个元素,建立 1 个最小堆;
    步骤 2 :遍历剩余元素,如果剩余元素小于堆顶元素,则丢弃或不作处理;如果剩余元素大于堆顶元素,则将其取代堆顶元素,并将当前堆调整为最小堆。
    步骤 3 :返回堆顶元素,即 nums[0],就是所要寻找的中位数。

    一点解释:
    不管是步骤 1、2 还是整个过程中,最小堆的栈顶元素必然满足:
    中位数 >= 最小堆的堆顶元素
    例如,[7,8,9,10,11,12,13] 中位数是 10 ,n 等于 7 ,(n+1)//2 等于 4 ,不管是取前 4 个数、后 4 个数、任意 4 个数,构造的最小堆的堆顶元素,最小为 7 ,最大为 10。
    因此,小于堆顶元素的元素,必然不可能是中位数,可以直接丢弃;中位数只有可能在最小堆、剩余元素中。

    实现:

    # coding:utf-8
    #from heap_sort import filter_down
    
    
    def filter_up(nums, p, n):
            parentIdx = p
            rootVal = nums[parentIdx]
    
            while 2*parentIdx+1 <= n-1:
                    kidIdx = 2*parentIdx+1
    
                    if kidIdx != n-1 and nums[kidIdx] > nums[kidIdx+1]:
                            kidIdx += 1
    
                    if rootVal < nums[kidIdx]:
                            break
                    else:
                            nums[parentIdx] = nums[kidIdx]
    
                    parentIdx = kidIdx
    
            nums[parentIdx] = rootVal
    
    
    def changeToMinHeap(nums, n):
            ''' 建立最小堆 '''
            for index in range(n//2-1, -1, -1):
                    filter_up(nums, index, n)
    
    
    def find_median(nums, n):
    
            assert n%2 == 1
    
            aboutHalf = (n+1)//2
    
            changeToMinHeap(nums, aboutHalf)
    
            pointer = aboutHalf
    
            for index in range(aboutHalf, n):
                    if nums[index] > nums[0]:
                            nums[0] = nums[index]
                            changeToMinHeap(nums, aboutHalf)
    
            return nums[0]
    
    
    def test():
            nums = list(range(4, 10)) + list(range(0, 4)) + list(range(10, 15))
            print('nums:', nums)
    
            assert find_median(nums, 15) == 7
    
            print('Pass!')
    
    
    if __name__ == '__main__':
            test()
    
    

    复杂度分析:

    暂时略。。

    参考文献:

    1. 无序数组的中位数
    2. 让人眼前一亮的算法!求无序数组的中位数

    算法 2 (建立最大堆、最小堆)

    时间复杂度

    O(n)

    参考文献:

    1. 无序数组中求中位数
    2. 【算法】无序数组中求中位数
    3. 试用O(n)来实现求出一个无序数组的中位数

    其他参考文献:

    1. 求一个无序数组的中位数
    2. 求中位数,快速选择算法
    展开全文
  • 问题: 从一个无序数组中找出中位数 这个类似于topk的问题,可以跟topK问题一起解决 解法:1.可以使用小顶堆,堆的大小为数组的一半,遍历一遍以后,输出堆顶元素即可。2.使用快排+二分,找一个基数,通过快排...
  • 无序数组中位数

    2021-04-04 09:27:11
    1.无序数组中位数 思路一 把无序数组排好序,取出中间的元素 时间复杂度 采用普通的比较排序法 O(N*logN) 如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N). 思路二 (1)将前(n+1)/2个...
  • 无序数组当中的中位数(快排思想,选中关键字,高低交替扫描) 示例: [@"1",@"9",@"6",@"8",@"3",@"2"] 输出: @"3" */ + (void)findMedianValue { NSMutableArray *array = [NSMutableArray ...
  • 无序数组中位数

    2019-10-01 11:38:42
    比如:{1,3,2,5,4} 中位数为3 {1,3,2,5,4,6}中位数为3.5 解析 排序 当然 排序啊。快排。 最小堆 首先将数组的前(n+1)/2个元素建立一个最小堆。 然后,对于下一个元素,和堆顶的元素比较,如果...
  • 无序数组中位数可以快排,然后直接去array[mid]即可,但这确实还不够快,因为我们的任务是找到中位数,而没有说要对这个数组排序,即只要array[mid]是中位数即可,array[0…mid]之间数据可以是无序的,只要小于...
  • 寻找无序数组中位数

    千次阅读 2017-08-06 22:13:40
    题目:求一个无序数组中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能高 提示:考虑堆或者快排思想解决。
  • 无序数组中位数

    2021-09-09 22:37:15
    无序数组排序,然后可以直接得到该数组的中位数,时间复杂度为O(nlogn)。 2. 利用快排思想寻找第K大的数(时间复杂度为O(n)) 先挑选一个数作为标准,以该元素为支点,将数组划分为两部分。 这个问题可以抽象...
  • 给一个无序数组array和数组长度n,找出其中的中位数(这里考虑n为奇数) Sample: ***** Input: ***** @[@(500),@(120),@(7),@(220),@(3),@(8),@(4),@(200),@(100) ***** Output: ***** 100 解法一:将数组...
  • 中位数,就是数组排序后处于数组最中间的那个元素。...思路1:将数组排序,然后直接从排序数组中找出中位数。时间复杂度取决于排序算法,最快是快速排序,O(nlogn),或者是非比较的基数排序,时间为O(n),空间为O...
  • 求一个无序数组中位数(Python)

    千次阅读 2018-07-12 10:31:17
    最简单的方法是先将数组排序,然后找中位数。但此种方法肯定不是最优的。一个比较好的做法是利用小顶堆。思路如下:1.取前len(nums)/2个元素建立小顶堆。可以知道堆顶元素是前len(nums)/2个元素中最小的。2.从第len...
  • 求一个无序数组中位数

    千次阅读 2017-08-05 14:34:09
    求一个无序数组中位数,如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能低。 解决方案一:采用堆排序思想 1、将前(n+1)/2个元素调整为一个...
  • 算法-再探无序数组中位数问题算法-再探无序数组中位数问题 算法-再探无序数组中位数问题 给定一个无序数组,求无序数组的中位数 本问题在前面写的博客里面提到过算法-TopK相关的问题
  •   中位数(又称中值,英语:Median),统计学中的专有名词,代表一个样本、种群或概率...  面试时,大家是不是经常被问到,怎么求一个无序数组(长度为n)的中位数?   面试官:知道什么是中位数吗?   ...
  • 题目:利用快排思想求一个无序数组中位数 对于一个有序数组arr来说: 如果数组长度为奇数,中位数为中间的那个数,即arr[arr.length/2] 如果数组长度为偶数,中位数为中间的两个数的平均值,即(arr[length/2] + ...
  • 和求无序数组中位数。 例题: 1 . int a[] = { 12, 13, 12, 13, 19, 18, 15, 12, 15, 16, 17 },要求对数组a进行排序,要求时间复杂度为O(N) 2.求一个无序数组中位数。 如:{ 2, 5, 4, 9, 3, 6, 8, 7, 1 }的...
  • 无序数组中找到中位数

    千次阅读 2017-09-19 19:37:11
    LeetCode中有对两个有序数组求他们的共同的中位数,就是在两个数组中各取第k/2个数,比较大小,因为是有序的,所以小的那个所在的数组之前的k/2个数都是属于他们中位数之前的,所以去除了k/2个数,在剩下的数组中...
  • python 实现在无序数组中找到中位数

    千次阅读 2019-07-16 21:32:11
    1,求一个无序数组中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低 2, 例如: lists = [3, 2, 1, 4] , 中位数为 ...
  • 无序数组中中位数

    2021-03-22 15:05:50
    } 再取中位数 function findMid(arr) { if (arr.length % 2 == 1) { return arr[Math.floor(arr.length / 2)]; } else { return (arr[arr.length / 2 - 1] + arr[arr.length / 2]) / 2 } } 结果 console.log(find...
  • 1. 选取第一个元素为基数,分别从右(high)往左(high--)查找,找到一个比基数小的,进行位置交换, 直到 low == high,结束一次排序;然后从 左 往右查找,找到一个比基数大的,进行位置交换,直到 low == ...
  • 若数组有奇数个元素,中位数是a[(n-1)/2];若数组有偶数个元素,中位数为a[n/2-1]和a[n/2]两个数的平均值。这里为方便起见,假设数组为奇数个元素。 思路一:把无序数组排好序,取出中间的元素。时间复杂度取决于...
  • 本文实例讲述了C++算法之在无序数组中选择第k小个的实现方法。分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的,如k=1为最小数,k=n为最大。这里数组可以是有重复的值! 下面是自己写的...
  • O(n)时间实现求出一个无序数组中位数 对于这个问题我起初就想到了多数派问题;那么受这个问题的影响,我就先到了一种方法:就是建立一个中间判断元素。left , right 两个计数器来记录,通过遍历数组的过程中,...
  • 求一个无序数组中位数

    千次阅读 2017-08-04 23:13:05
    问题描述求一个无序数组中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5,{2,5,4,9,3,6,8,7,1,0}的中位数为4和5。 要求:不能使用排序,时间复杂度尽可能低。 提示:考虑堆或者快排思想解决方法1:堆思路1: 分析...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,041
精华内容 17,616
关键字:

无序数组的中位数