长度为 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. 求中位数，快速选择算法

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. …
4. 第四趟，用堆方法从第一趟筛选出的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. 外存不够的情况

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

待查~

今早上在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)? 不过最官方的肯定是第三种方法。