O(n)的时间复杂度求中位数

O(n)中位数问题是指：在O(n)的时间复杂度内找到一个无序序列的中位数。

在开始O(n)时间复杂度求中位数之前，先手写一下快速排序。

快速排序的实现

Reference：
快速排序|菜鸟教程
白话经典算法系列之六 快速排序 快速搞定

快速排序的原理

如果想正序排序一个序列：

1. 从序列中找到一个 基准数 。
2. 分区：将序列中比基准数大的数字都放到基准数的右边，将序列中比基准数小的数字都放在基准数的左边。
   • 此时，序列被分成了三部分: 左序列 + 基准数 + 右序列。
   • 实现2的方法可以是 挖坑法 。
3. 对左序列和有序列进行排序即可（递归），直到左/右序列长度为1。

快速排序的复杂度

1. 时间复杂度：
   • 最好：O(nlogn)
   • 最坏：O(n^2)
   • 平均：O(nlogn)
2. 空间复杂度：O(nlogn)
3. 稳定性：不稳定

快速排序的实现1

void quick_sort(int a[], int left, int right){
    if (left >= right){
        return;
    }
    int l = left, r = right;
    int x = a[left]; // 选取当前序列最左边的数字为基准数

    while (l < r){
        while (l < r && a[r] >= x){
            r --;
        }
        if (l < r){
            a[l] = a[r];
            l ++;
        }
        while (l < r && a[l] < x){
            l ++;
        }
        if (l < r){
            a[r] = a[l];
            r ++;
        }
    }
    a[l] = x;
    quick_sort(a, left, l - 1);
    quick_sort(a, l + 1, right);
}

• 每一次快排都会确定一个位置，这个位置是l，大小是基准数。
• 如果我们想每一次都知道 快速排序确定的位置 ，那么可以写一个partition函数。（事实上，这是在为O(n)解决中位数问题做铺垫。）

快速排序的实现2——partition函数

int partition(int a[], int l, int r){
    int x = a[l];
    while (l < r){
        while (l < r && a[r] >= x){
            r --;
        }
        if (l < r){ 
            a[l] = a[r];
            l ++;
        }
        while (l < r && a[l] < x){
            l ++;
        }
        if (l < r){
            a[r] = a[l];
            r --;
        }
    }
    a[l] = x;
    return l;
}

void Q_sort(int a[], int l, int r){
    if (l < r){
        int index = partition(a, l, r);
        Q_sort(a, l, index-1);
        Q_sort(a, index+1, r);
    }
}

• partiton()负责将获得每一次进行步骤2：分区得到的基准数在最终递增序列中的 位置 。

• Q_sort()中的index就是该位置。根据该位置将序列分为左右序列。

有了partition函数，就可以实现O(n)时间复杂度找中位数的工作了。

基于partition函数的O(n)中位数

显然，如果没有O(n)的限制，那么一个直白的想法是：将无序序列排序，然后输出序列的 第n/2个位置 的元素。

• n是序列的长度。
• 其实，对于中位数应该分情况讨论：
  • 当 n 是奇数时，中位数是a[n/2]；
  • 当 n 是偶数时，中位数是(a[n/2] + a[n/2 - 1]) / 2.0。

上述算法的时间复杂度是O(nlogn)。

考虑到，对于partition函数，每一个可以确定一个位置！ 那么，假设这个位置是index，那么对于中位数的位置pos:

• 如果index = pos，显然，找到了中位数a[index]。
• 如果index > pos，显然，中位数位于区间[l, index-1]。
  • 此时，只需对区间[l, index-1]再次进行partition操作即可。
• 如果index < pos，显然，中位数位于区间[index+1, r]。
  • 同上。

根据上述思想，编写函数getMidNumber():

int getMidNumber(int a[], int l, int r, int pos){
    while (true){
        int index = partition(a, l, r); // 获得基准数的位置
        if (index == pos){
            return a[index];
        }else if (index > pos){ // 只需要在[l, index-1]区间内找pos位置即可
            r = index - 1;
        }else { // 只需要在[index, r]区间内找pos位置即可
            l = index + 1;
        }
    }
    return -1; // 一般程序不会到这里
}

• 其中，pos的含义是中位数的位置：
  • 当序列长度为奇数时，pos = n/2
  • 当序列长度为偶数时，pos = n/2 或 n/2 - 1

比如，可以编写如下代码测试：

int main(){
    int a[] = {10, 8, 3, 5, 6, 2, 1, 7, 9, 4};
    int aLen = sizeof(a) / sizeof(int);

    if (aLen&1){
        cout << "Mid= " << getMidNumber(a, 0, aLen-1, aLen/2) << endl;
    }else{
        cout << "Mid= " << (getMidNumber(a, 0, aLen-1, aLen/2) + getMidNumber(a, 0, aLen-1, aLen/2-1)) / 2.0 << endl;
    }

    return 0;
}

• aLen是序列a的长度。

时间复杂度分析

最坏：O(n^2)

• 假设一种极端情况，每一次选取的基准数都是序列中最小的那个数字，因此partition函数会依次返回0,1,2...n/2，每一次partition函数都需要O(n)的时间复杂度。因此，最坏的时间复杂度为O(n^2)。

最好: O(n)

• 假设一种完美情况，第一次得到的基准数就是中位数，那么只需要执行一次partition函数，因此时间复杂度是O(n)。

平均: O(n)
数学不好，证明不会。据 他们 说该算法的 期望 时间复杂度是O(n)。
这好像是涉及 主定理MasterTheorem。搜了好多网页博客也没看懂。

Reference：
主定理 Master Theorem

拓展：找序列中第K大的数字

其实找中位数就是找序列中第n/2大的数字。

因此找需要调用getMidNumber(a, 0, aLen-1, k)即可找到序列中第k大的数字了。

大佬的一种更简洁的写法

O(n)求中位数和第k大数

2020.9.26 14:41 周六

方法

使用python的内置方法list.sorted()对序列进行排序取中位数

实现

设数据为test：

#author：FarryNiu
test = [5,5,6,4,5,4,7,1,10,

题目：在一个文件中有 10G 个整数，乱序排列，要求找出中位数。内存限制为 2G。只写出思路即可（内存限制为 2G的意思就是，可以使用2G的空间来运行程序，而不考虑这台机器上的其他软件的占用内存）。

关于中位数：数据排序后，位置在最中间的数值。即将数据分成两部分，一部分大于该数值，一部分小于该数值。中位数的位置：当样本数为奇数时，中位数=(N+1)/2 ; 当样本数为偶数时，中位数为N/2与1+N/2的均值（那么10G个数的中位数，就第5G大的数与第5G+1大的数的均值了）。

分析：明显是一道工程性很强的题目，和一般的查找中位数的题目有几点不同。

1. 原数据不能读进内存，不然可以用快速选择，如果数的范围合适的话还可以考虑桶排序或者计数排序，但这里假设是32位整数，仍有4G种取值，需要一个16G大小的数组来计数。
2. 若看成从N个数中找出第K大的数，如果K个数可以读进内存，可以利用最小或最大堆，但这里K=N/2,有5G个数，仍然不能读进内存。
3. 接上，对于N个数和K个数都不能一次读进内存的情况，《编程之美》里给出一个方案：设k<K,且k个数可以完全读进内存，那么先构建k个数的堆，先找出第0到k大的数，再扫描一遍数组找出第k+1到2k的数，再扫描直到找出第K个数。虽然每次时间大约是nlog(k)，但需要扫描ceil(K/k)次，这里要扫描5次。

解法：首先假设是32位无符号整数。
1.读一遍10G个整数，把整数映射到256M个区段中，用一个64位无符号整数给每个相应区段记数。
说明：整数范围是0 - 2^32 - 1，一共有4G种取值，映射到256M个区段，则每个区段有16（4G/256M = 16）种值，每16个值算一段， 0～15是第1段，16～31是第2段，……2^32-16 ～2^32-1是第256M段。一个64位无符号整数最大值是0～8G-1，这里先不考虑溢出的情况。总共占用内存256M×8B=2GB。
2.从前到后对每一段的计数累加，当累加的和超过5G时停止，找出这个区段（即累加停止时达到的区段，也是中位数所在的区段）的数值范围，设为[a，a+15]，同时记录累加到前一个区段的总数，设为m。然后，释放除这个区段占用的内存。
3.再读一遍10G个整数，把在[a，a+15]内的每个值计数，即有16个计数。
4.对新的计数依次累加，每次的和设为n，当m+n的值超过5G时停止，此时的这个计数所对应的数就是中位数。

总结：
1.以上方法只要读两遍整数，对每个整数也只是常数时间的操作，总体来说是线性时间。
2. 考虑其他情况。若是有符号的整数，只需改变映射即可。若是64为整数，则增加每个区段的范围，那么在第二次读数时，要考虑更多的计数。若过某个计数溢出，那么可认定所在的区段或代表整数为所求，这里只需做好相应的处理。噢，忘了还要找第5G+1大的数了，相信有了以上的成果，找到这个数也不难了吧。
3. 时空权衡。花费256个区段也许只是恰好配合2GB的内存（其实也不是，呵呵）。可以增大区段范围，减少区段数目，节省一些内存，虽然增加第二部分的对单个数值的计数，但第一部分对每个区段的计数加快了（总体改变？？待测）。
4. 映射时尽量用位操作，由于每个区段的起点都是2的整数幂，映射起来也很方便。