精华内容
下载资源
问答
  • python 实现在无序数组中找到中位数
    2020-11-30 23:31:17

    一,问题描述

    1,求一个无序数组的中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低

    2, 例如:

    lists = [3, 2, 1, 4] , 中位数为 = (2+3)/2 = 2.5

    lists = [3, 1, 2] , 中位数为 2

    3, 算法思想:

    利用快速排序思想(但是并不是全部使用):任意挑选一个元素,以该元素为key, 划分数组为两个部分,如果左侧数组长度刚好为(n-1)/2, 那么key就为中位数, 若左侧数组长度 < (n-1)/2 , 那么中位数点在右侧,反之,中位数在左侧。然后进入相应的一侧继续寻找中位

    平均时间复杂度为O(n)

    二,程序

    1,

    class Solution(object):

    def findmedian(self, lists):

    if not lists or len(lists) == 0:

    return []

    n = len(lists)

    if n % 2 == 0:

    a = self.partition(lists, n/2, 0, n-1)

    b = self.partition(lists, n/2-1, 0, n-1)

    mid = (lists[a]+lists[b])/ (2 * 1.0)

    return mid

    else:

    mid = self.partition(lists, n/2, 0, n-1)

    return lists[mid]

    def partition(self, lists, k, start, end):

    key = lists[start]

    left, right = start, end

    while left < right:

    while left < right and lists[right] > key:

    right = right - 1

    lists[left] = lists[right]

    while left < right and lists[left] < key:

    left = left + 1

    lists[right] = lists[left]

    lists[left] = key

    if left == k:

    return left

    elif left > k:

    return self.partition(lists, k, start, left-1)

    else:

    return self.partition(lists, k, left+1, end)

    if __name__ == "__main__":

    sol = Solution()

    lists = [2, 5, 4, 9, 3, 6, 8, 7, 1]

    # lists = [1, 2]

    data = sol.findmedian(lists)

    print("中位数 = %s" % data)

    更多相关内容
  • 主要介绍了python 实现在无序数组中找到中位数方法,具有很好对参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 无序数组求中位数

    千次阅读 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. 求中位数,快速选择算法
    展开全文
  • 无序数组找中位数

    2021-04-04 09:27:11
    1.无序数组找中位数 思路一 把无序数组排好序,取出中间的元素 时间复杂度 采用普通的比较排序法 O(N*logN) 如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N). 思路二 (1)将前(n+1)/2个...

    1.无序数组找中位数

    1. 思路一
      把无序数组排好序,取出中间的元素
      时间复杂度 采用普通的比较排序法 O(N*logN)
      如果采用非比较的计数排序等方法, 时间复杂度 O(N), 空间复杂度也是O(N).

    2. 思路二
      (1)将前(n+1)/2个元素调整为一个小顶堆
      (2)对后续的每一个元素,和堆顶比较,如果小于等于堆顶,丢弃之,取下一个元素。 如果大于堆顶,用该元素取代堆顶,调整堆,取下一元素。重复2.2步
      (3)当遍历完所有元素之后,堆顶即是中位数。
      注:如果数组元素的个数是奇数,取数组前(size+1)/2个元素建堆,如果是偶数则取前 size/2 个元素建堆。但如果是数据流,数据个数是动态变动的,则应采用小根堆+大根堆的办法,具体见本文第5点介绍。

    3. 思路三
      找中位数也可以用快排分治的思想。具体如下:
      (1)任意挑一个元素,以改元素为支点,划分集合为两部分,如果左侧集合长度恰为 (n-1)/2,那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧,反之,中位数在左侧。
      (2)进入相应的一侧继续寻找中位点。
      注:可参考快排思想实现Top K

    拓展:查找N个元素中的第K个小的元素,假设内存受限,仅能容下K/4个元素
    分趟查找:

    1. 第一趟,用堆方法查找最小的K/4个小的元素,同时记录剩下的N-K/4个元素到外部文件。
    2. 第二趟,用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素,同时记录剩下的N-K/2个元素到外部文件。
    3. 第四趟,用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素,这是的第K/4小的元素即使所求。

    https://blog.csdn.net/zdl1016/article/details/4676882


    2.将十进制数字转化为X 进制的字符串

    //将十进制数转化为X进制字符串 
    string trans(int num, int base){
    	string str;
    	while(num > 0){
    		if(num % base < 10)
    			str += num % base + '0';
    		else
    			str += num % base - 10 + 'A';
    		num = num / base;
    	}
    	reverse(str.begin(),str.end());
    	
    	return str;
    }
    

    3.找出字符串中第k次出现的字符

    1. 思路一
      遍历这个字符串(缺点是要对这个字符串查找好多次)
    2. 思路二
      (1) 先创建一个数组然后这个数组你就放成256个元素。
      (2) 把这个字符串转化成ASCLL码进行查找。(因为ASCLL码的范围比较小)
      (3) 当我们发现字符串中出现a(a的ASCLL为97)的时候,我们可以把刚才256个元素中下边为97的元素的值加一。
    char find_first_K(string str, int K)
    {
    	int count[256] = { 0 };
    	for (char ch : str) ++count[ch];
    
    	for (char ch : str) {
    		if (count[ch] == K)
    			return ch;
    	}
    
    	return '0';
    }
    

    5.找出数据流中的中位数

    在这里插入图片描述

    注意:始终保证小根堆A中元素个数不少于大根堆B中的元素个数,即A、B元素相等时,将B中最大元素加入A,否则将A中最小元素加入B,来维持元素个数平衡。

    class MedianFinder {
    private:
        priority_queue<int,vector<int>, greater<int>> A;    //小根堆
        priority_queue<int,vector<int>, less<int>> B;       //大根堆
    
    public:
        //插入新元素
        void addNum(int num) {
            if(A.size()==B.size()){ //把B中最大元素加入到A
                B.push(num);
                A.push(B.top());
                B.pop();
            }else{                  //把A中最小元素加入到B
                A.push(num);
                B.push(A.top());
                A.pop();
            }
        }
        
        //查找当前中位数
        int findMedian() {
            return A.size()==B.size()?(A.top()+B.top())/2.0:A.top();
        }
    };
    

    6.英文字符串流和中文字符串流如何分词

    一种对英文字符串进行分词的方法:https://d.wanfangdata.com.cn/periodical/jsjyyyj200707016

    字典与统计相结合的中文分词方法:https://d.wanfangdata.com.cn/periodical/xxwxjsjxt200609039

    暴力方法:

    1. 英文分词:根据字符串中的空格、标点符号进行分词。
    2. 中文分词:固定两个字为一词进行拆分。

    7.10亿QQ号去重

    1. 内存够的情况

    分段、map、多线程。

    1. 分段:哈希分桶,根据哈希值对桶数目取模得到对应桶号。
    2. map:需要计数采用unordered_map去重;不需要计数采用set去重。
    3. 多线程:将数据进行哈希分桶之后,各桶内map的去重可以采用多线程执行。

    2. 内存不够的情况

    思路一:bitmap

    位图bitmap:每个int数字只用一个比特位来做标记

    位图的操作(算法)基本依赖于下面3个元操作:

    set_bit(char x, int n); //将x的第n位置1,可以通过x |= (1 << n)来实现
    
    clr_bit(char x, int n); //将x的第n位清0,可以通过x &= ~(1 << n)来实现
    
    get_bit(char x, int n); //取出x的第n位的值,可以通过(x >> n) & 1来实现
    

    比如,要对数字int x = 1848105做标记,就可以调用set_bit(bit_map[x/8], x%8);

    除法看做求“组编号”,x/8即是 以8个位为一个小组,分组到编号为idx = x/8的bit_map元素中,然后在组内偏移lft = x%8个比特位。

    10亿数字(int 32位):10^8 * 32 / 8 = 40亿字节 / 1024 ≈ 400万 KB / 1024 ≈ 4000 MB / 1024 ≈ 4 GB
    int 32位所需bitmap大小:2^32 / 8 = 2^29 字节 / 1024 = 2^19 KB / 1024 = 2^9 MB = 512 MB

    10亿数字(long long 64位):4 GB * 2 = 8GB
    long long 64位所需bitmap大小:2^64 / 2^23 = 2^41 MB / 1024 = 2^31 GB / 1024 = 2^21 TB / 1024 = 2048 PB = 2 EB

    https://www.cnblogs.com/zhanghaiba/p/3594559.html

    思路二:多路归并排序

    问题:如何给100亿个数字排序?

    注:100亿个 int 型数字放在文件里面大概有 37.2GB

    1. 把这个37GB的大文件,用哈希分成1000个小文件,每个小文件平均38MB左右(理想情况),把100亿个数字对1000取模,模出来的结果在0到999之间,每个结果对应一个文件,所以我这里取的哈希函数是 h = x % 1000,哈希函数取得”好”,能使冲突减小,结果分布均匀。
    2. 按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.
    3. 从堆顶文件里读一个元素并写入输出文件.
    4. 同时按读的那个文件的下一个元素的值调整堆.
    5. 若第3步已到达文件结尾.则从堆中删除该输入流.
    6. 如果堆中还有元素. 回到第2步.

    3. 外存不够的情况

    考虑是不是可以进行分布式处理

    待查~


    展开全文
  • 找出无序数组中位数的方法

    千次阅读 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)? 不过最官方的肯定是第三种方法。

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

    千次阅读 2017-09-19 19:37:11
    中位数就是最中间那个数或中间两个数的和的平均数 求中位数其实就是求第k大或者第k小的数 LeetCode中有对两个有序数组求他们的共同的中位数,就是在两个数组中各取第k/2个数,比较大小,因为是有序的,所以小的...
  • 无序数组中求中位数

    千次阅读 2017-06-08 16:34:15
    题目现有一些随机生成的数字要将其依次传入,请设计一个高效算法,对于每次传入一个数字后,算出当前所有传入数字中位数。(若传入了偶数个数字则令中位数为第n/2小的数字,n为已传入数字个数)。 给定一个int数组A...
  • 解决快速求出无序数组的中位数 方法一:快排思想 思想:利用快排思想。 具体解释,其实简单,我们利用的就是一个东西,快排每次选取一个数,然后把比这个数字小的扔到前面,把比这个数字大的数放到前面,那么对取的...
  • 1.算法题一:无序数组的中位数 (快排思想O(N) 时间复杂度) package com.lightsword.leetcodeproblems import org.junit.jupiter.api.Test import java.util.* /** * 1.算法题一:无序数组的中位数 (快排思想O(N) ...
  • 【算法】无序数组中求中位数

    千次阅读 2017-10-05 11:23:31
    给定一个int数组A,为传入的数字序列,同时给定序列大小n,请返回一个int数组,代表每次传入后的中位数。保证n小于等于1000 或者 求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5。 要求:不能使用...
  • 找出一个无序数组的中位数

    千次阅读 2019-03-25 08:47:40
    要解决这个问题首先要了解什仫是中位数,所谓的中位数就是在一组有序的数字中找到中间的那个数字。如果数字的个数是奇数则直接返回中间的那个数,如果数字的个数是偶数此时这组数据的中位数有两个,取中间两个数的...
  • 求一个无序数组的中位数

    千次阅读 2017-08-08 23:37:29
    求一个无序数组的中位数。 如:{2,5,4,9,3,6,8,7,1}的中位数为5。 要求:不能使用排序。 暂时只考虑奇数时的情况,偶数有时会规定相邻两个数的平均数。 下面的分析都只考虑奇数的情况。 思路1:对前(n+1)/2个...
  • 问题 有5亿个整数,没有排序。找到他们的中位数 ...第一次扫描后,通过统计就可以知道,中位数在哪个区域内,以及它是这个区域的第几大的数字。 进行第二次扫描,这次只统计落到目标区域内的数字,同...
  • 在一个文件中有 10G 个整数,乱序排列,要求找出中位数。内存限制为 2G。 不妨假设10G个整数是64bit的。 2G内存可以存放256M个64bit整数。 我们可以将64bit的整数空间平均分成256M个取值范围,用2G的内存...
  • O(n)的时间复杂度求中位数

    千次阅读 2020-09-26 14:45:14
    O(n)中位数问题是指:在O(n)的时间复杂度内找到一个无序序列的中位数。 在开始O(n)时间复杂度求中位数之前,先手写一下快速排序。 快速排序的实现 Reference: 快速排序|菜鸟教程 白话经典算法系列之六 快速排序 ...
  • 时间复杂度为O(n)的找中位数算法源代码
  • 中位数(C语言)

    万次阅读 2017-06-19 17:50:46
    计算有限个数的数据的中位数的方法是:把所有的同类数据按照大小的顺序排列。如果数据的个数是奇数,则中间那个数据就是这群数据的中位数;如果数据的个数是偶数,则中间那2个数据的算术平均值就是这群数据的中位数...
  • 在一个无序数组找到3个数字组成数最小,要求这三个数字的索引是按序排列, 有不对的请直接与博主沟通。 /* 从一组无序找到组合最小的N位数。 时间复杂度和空间复杂都都N*M,N为位数(三位数N=3),M为数组长度 ...
  • System.out.println("请输入10个数字,每个数字之间用“,”分割:"); String str_numbers = br.readLine(); br.close(); str_numbers = str_numbers.replaceAll("\\s", ""); String [] str = str_numbers.split(",...
  • 为了匹配字符串数字,MySQL的语法如下:select*fromyourTableNamewhereyourColumnNameregexp'[0-9]';要了解上述语法,让我们创建一个表-mysql>createtableDemoTable1841(Codevarchar(20));使用插入命令在表...
  • 【数据结构】中位数

    2019-11-26 22:15:31
    描述 ...给出一组无序整数,求出中位数,如果求最中间两个数的平均数,向下取整即可(不需要使用浮点数) 输入 该程序包含多组测试数据,每一组测试数据的第一行为N,代表该组测试数据包含的数据个...
  • Excel如何提取单元格的部分文字或单元格数字 Excel如何提取单元格的部分文字或单元格数字,整理了Excel所有的提取要求,写成了一个公式翻译工具。 支持以下提取方式,输入提取要求,自动生成Excel...
  • Python3字符串数字提取方法

    千次阅读 2020-11-21 02:58:36
    原博文2018-10-28 17:07 −## Python3字符串数字提取方法 - **re.sub(pattern, repl, string, count=0, flags=0)** ```1 totalCount = '100abc' 2 totalCount = re.sub("\D", "", totalCount) ...相关推荐2019...
  • Python-随机生成20位数字

    千次阅读 2021-11-10 15:53:59
    结合时间随机生成20位数字 def get_random_num20(): """ 返回20有效数字 """ now = datetime.datetime.now().strftime("%Y%m%d%H%M%S") random_num = "%06d" % random.randint(0, 1000000) return '%s%s' % ...
  • js超简单实用随机产生1-100个数字不重复
  • 给定一个整数序列,求中位数

    千次阅读 2019-01-20 15:07:22
    给定一个整数序列,求中位数。如果序列个数为奇数,中位数为升序的中间位置,如果是偶数,这位升序的中间两个数的平均值。 输入: 输入包含多组测试数据,每一组第一行为n(n&lt;104)表示这个序列的个数,接下来...
  • 加权中位数

    2019-09-24 10:18:12
    要求找出这一无序数列中的中位数。 1. 直接解法,先对该数列和权重排序。然后找出累计权重为中位数数字。 时间复杂度为排序的 O(nlog(n)+n) 2 import numpy as np 3 4 def weighted_median(data, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 47,827
精华内容 19,130
热门标签
关键字:

无序数字中位数