精华内容
下载资源
问答
  • 无序数组找中位数

    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. 外存不够的情况

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

    待查~


    展开全文
  • 无序数组找中位数可以快排,然后直接去array[mid]即可,但这确实还不够快,因为我们的任务是找到中位数,而没有说要对这个数组排序,即只要array[mid]是中位数即可,array[0…mid]之间数据可以是无序的,只要小于...

    无序数组找中位数 C++,Python 快排思想实现

    无序数组找中位数可以快排,然后直接去array[mid]即可,但这确实还不够快,因为我们的任务是找到中位数,而没有说要对这个数组排序,即只要array[mid]是中位数即可,array[0…mid]之间数据可以是无序的,只要小于array[mid]即可,而对右半区间也一样。

    这里我们用快排的思想来实现,如果还不了解快排的同学可以到该博客去学习一下先

    C/C++:

    int PartSort(int *arr, int start, int end)
    {
        int left = start;
        int right = end;
        int key = arr[end];   //选取关键字
        while (left < right)
        {
            while (left < right && arr[left] <= key)  //左边找比key大的值
            {
                ++left;
            }
            while (left < right && arr[right] >= key)  //右边找比key小的值
            {
                --right;
            }
            if (left < right)
            {
                swap(arr[left], arr[right]);  //找到之后交换左右的值
            }
        }
        swap(arr[right], arr[end]);
        return left;
    }
    //求一个无序数组的中位数
    int GetMidNumNoSort1(int *arr,int size)
    {
        assert(arr);
        int start = 0;
        int end = size - 1;
        int mid = (size - 1) / 2;
        int div = PartSort(arr, start, end);
        while (div != mid)
        {
            if (mid < div)   //左半区间找
                div = PartSort(arr, start, div - 1);
            else    //左半区间找
                div = PartSort(arr, div + 1, end);
        }
        return arr[mid];   //找到了
    }
    

    Python:

    # -*- coding: utf-8 -*-
    # @File   : find_middle.py
    # @Author : Runpeng Zhang
    # @Date   : 2020/4/12
    # @Desc   : 无序数组找中位数
    
    
    a = [3, 0, 1, 2, 8, 4, 6]
    
    
    def part_sort(a, start, end):
        left = start
        right = end
        key = a[end]
        while left < right:
            while a[left] <= key and left < right:
                left += 1
            while a[right] > key and left < right:
                right -= 1
            a[left], a[right] = a[right], a[left]
        a[right], a[end] = a[end], a[right]
        return left
    
    
    def main(a):
        start = 0
        end = len(a) - 1
        mid = (start + end) // 2
        div = part_sort(a, start, end)
        while div != mid:
            if div < mid:
                div = part_sort(a, div + 1, end)
            else:
                div = part_sort(a, start, div - 1)
        return a[mid]
    
    
    print(main(a))
    
    
    展开全文
  • 主要介绍了python 实现在无序数组中找到中位数方法,具有很好对参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 基本思路:对数组进行排序,直接访问数组中位数 double MIDnum(vector<int>& array) { if(array.empty()) return -1; int midIndex = (array.size() - 1) / 2; sort(array.begin(), array.end()); if...

    一.利用排序进行查找中位数

    基本思路:对数组进行排序,直接访问数组中位数

    double MIDnum(vector<int>& array) {
        if(array.empty())
            return -1;
    	int midIndex = (array.size() - 1) / 2;
    	sort(array.begin(), array.end());
    	if (array.size() % 2 == 1) {
    		return (double)array[midIndex];
    	}
    	return ((double)array[midIndex] + (double)array[midIndex + 1]) / 2;
    }

    二.类似于快速排序,采用的是分而治之的思想.

    基本思路:任意挑选一个元素,以该元素为基准点,将数组分为两部分.左部分都是小于基准点的,右部分都是大于基准点的.如果运气好的话,基准值正好就是中位数.

    int partion(vector<int>& array, int begin, int end) {
    	int start = begin;
    	int key = array[begin];
    	while (begin < end) {
    		while (begin < end && array[end] >= key) {
    			end--;
    		}
    		while (begin < end && array[begin] <= key) {
    			begin++;
    		}
    		swap(array[begin], array[end]);
    	}
    	swap(array[start], array[begin]);
    	return begin;
    }	
    
    double getNum(vector<int>& array, int midIndex) {
    	int left = 0;
    	int right = array.size() - 1;
    	int index = -1;
    	while (index != midIndex) {
    		index = partion(array, left, right);
    		if (index > midIndex) {
    			right = index - 1;
    		}
    		else if (index < midIndex) {
    			left = index + 1;
    		}
    		else
    			break;
    	}
    	return (double)array[index];
    }
    double midNum(vector<int>& array) {
    	if (array.empty()) {
    		return -1;
    	}
    	int midIndex = (array.size() - 1) / 2;
    	if (array.size() % 2 == 1) {
    		return getNum(array, midIndex);
    	}
    	return (getNum(array, midIndex) + getNum(array, midIndex + 1)) / 2;
    }

    三.利用最小堆查找中位数

    基本思路:首先将数组的前(n+1)/2个元素建立最小堆.后序元素进行判断入堆或舍弃.下一个元素与堆顶元素进行对比,如果大于堆顶元素则删除堆顶元素,该元素入堆,否则什么都不做.

    double MidNum(vector<int>& array) {
        if(array.empty())
            return -1;
    	int sz = array.size() / 2 + 1;
    	cout << sz << endl;
    	priority_queue<int,vector<int>,greater<int>> pq;
    	for (int i = 0; i < sz; i++) {
    		pq.push(array[i]);
    	}
    	for (int i = sz; i < array.size(); i++) {
    		if (array[i] > pq.top()) {
    			pq.pop();
    			pq.push(array[i]);
    		}
    	}
    	if (array.size() % 2 == 1) {
    		return (double)pq.top();
    	}
    	double val1 = double(pq.top());
    	pq.pop();
    	double val2 = double(pq.top());
    	return (val1 + val2) / 2;
    }

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

    千次阅读 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])

    展开全文
  • 无序数组中位数(c语言版本)

    千次阅读 2019-03-22 16:06:41
    在面试时,会经常被问道,如何求解一个无序数组中位数?很多人往往都会第一感觉就是,先将该数组排序,然后出最中间的那个数,但是这种思路通常的时间复杂度最好是O(nlogn),更糟的情况下会到O(n^2),并不是最优...
  • 无序数组中位数的方法

    千次阅读 2020-01-13 13:10:48
    今早上在LintCode上做到了这种...找无序数组中位数我想着我之前逛知乎的时候遇到过,用最大堆和最小堆来做的。想了想,遇到这么多次,那就整理下方法吧。 这里中位数的定义是数组元素个数/2 1 直接排序中位数 直接...
  • 一,问题描述1,求一个无序数组中位数, (若数组是偶数,则中位数是指中间两个数字之和除以2,若数组是奇数,则中位数是指最中间位置。要求:不能使用排序,时间复杂度尽量低2, 例如:lists = [3, 2, 1, 4] , ...
  • 出一个无序数组中位数

    万次阅读 热门讨论 2017-08-04 14:01:25
    出一个无序数组中位数
  • 解决快速求出无序数组中位数 方法一:快排思想 思想:利用快排思想。 具体解释,其实简单,我们利用的就是一个东西,快排每次选取一个数,然后把比这个数字小的扔到前面,把比这个数字大的数放到前面,那么对取的...
  • 求一个无序数组中位数

    千次阅读 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个元素调整为一个...
  • 无序数组中位数

    千次阅读 2018-12-07 16:34:46
    长度为 n 的无序数组,求中位数,如何尽快的估算出中位数,算法复杂度是多少? 算法 1(建立最小堆): 如果数组中元素有奇数个,可以采用这种算法: 步骤 1 :可以将数组的前 (n+1)//2 个元素,建立 1 个最小堆; ...
  • 1. 选取第一个元素为基数,分别从右(high)往左(high--)查找,找到一个比基数小的,进行位置交换, 直到 low == high,结束一次排序;然后从 左 往右查找,找到一个比基数大的,进行位置交换,直到 low == ...
  • 中位数,就是数组排序后处于数组最中间的那个元素。说来有些麻烦,如果数组长度是奇数,最中间就是位置为(n+1)/2的那个元素。如果是偶数呢,标准的定义是位置为n/2和位置为n/2+1的两个元素的和除以2的结果,有些...
  • 寻找无序数组中位数

    千次阅读 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。 要求:不能使用排序,时间复杂度尽可能高 提示:考虑堆或者快排思想解决。
  • 中位数,就是数组排序后处于数组最中间的那个元素。...思路1:将数组排序,然后直接从排序数组中找中位数。时间复杂度取决于排序算法,最快是快速排序,O(nlogn),或者是非比较的基数排序,时间为O(n),空间为O...
  • 1.算法题一:无序数组中位数 (快排思想O(N) 时间复杂度) package com.lightsword.leetcodeproblems import org.junit.jupiter.api.Test import java.util.* /** * 1.算法题一:无序数组中位数 (快排思想O(N) ...
  • 无序数组当中的中位数(快排思想,选中关键字,高低交替扫描) 示例: [@"1",@"9",@"6",@"8",@"3",@"2"] 输出: @"3" */ + (void)findMedianValue { NSMutableArray *array = [NSMutableArray ...
  • O(n)时间实现求出一个无序数组中位数 对于这个问题我起初就想到了多数派问题;那么受这个问题的影响,我就先到了一种方法:就是建立一个中间判断元素。left , right 两个计数器来记录,通过遍历数组的过程中,...
  • 给一个无序数组array和数组长度n,出其中的中位数(这里考虑n为奇数) Sample: ***** Input: ***** @[@(500),@(120),@(7),@(220),@(3),@(8),@(4),@(200),@(100) ***** Output: ***** 100 解法一:将数组...
  • 求一个无序数组中位数(Python)

    千次阅读 2018-11-08 19:31:08
    最简单的方法是先将数组排序,然后找中位数。但此种方法肯定不是最优的。一个比较好的做法是利用小顶堆。思路如下: 1.取前len(nums)//2个元素建立小顶堆。可以知道堆顶元素是前len(nums)/2个元素中最小的。 2.从...
  • 来源:力扣(LeetCode) ... 题目: 给定两个大小为 m 和 n 的有序数组 ...请你出这两个有序数组中位数,并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例 1: nu...
  • 有一道题大概是这样的:有n条水平的线,知道线的纵坐标,选择一条线,使得这条线到所有线的距离之...那么在线数量为偶数的时候,这并不是传统的求中位数问题,而线数量为奇数的时候,则变成传统的中位数问题。求中位...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 46,507
精华内容 18,602
关键字:

无序数组找中位数

友情链接: wenxian.zip