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 周六

目录

•写在前面

•题目

•解法一

•解法二

•解法三

•结束

•写在前面

这道题比较经典，我当时在做的时候，想出了两种解决方案，不过总感觉算法不够优美，所以找到了另一种我觉得非常精妙的解法，利用了K最小数的思想去解决这道题，很值得讲一下，不知道K最小数的，可以参考我另一篇文章，点击这里跳转就可以了。下面我废话不多说，直接开始讲解。

•题目

首先先把题目呈上来，具体题目如下：

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。请你找出这两个有序
数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。你可以假
设 nums1 和 nums2 不会同时为空。
测试用例：
nums1 = [1, 3]
nums2 = [2]
测试结果：则中位数是 2.0

•解法一

怎么说解法一呢，其实可以把解法一当成暴力解法，对这道题进行硬解。但是如果仔细看要求的话就会发现，题目里要求了时间复杂度是O(log(m + n))，所以这种解法不能满足要求，不过因为我当时先看到的是没有O(log(m + n))要求的题目，所以就直接暴力解决了（对于有些题目，暴力不失为一种省力的好办法，小声bb）。这个解法没什么好讲的，我就大概说一下思路。

具体思路就是，将两个数组使用归并的思想，进行整合，然后求解。（ps：别说直接合起来，然后排序，你要是这样做的话，算法老师的棺材板都压不住），直接上代码。当然啦，下面代码直接整合成了一个数组，其实我们也可以不用真的整合数组，只要通过不断比对，然后记录值就可以了（注意边界问题）。这种解法的时间复杂度是O(m + n)哦。

public static double Test4S2(int[] nums1, int[] nums2) {
        List<Integer> array = new ArrayList<>(10);

        int size1 = nums1.length;
        int size2 = nums2.length;
        int index1 = 0;
        int index2 = 0;

        while(index1 != size1 || index2 != size2){
            if(index1 == size1){
                for (int i = index2; i < size2; i++){
                    array.add(nums2[i]);
                }
                break;
            }else if (index2 == size2){
                for (int i = index1; i < size1; i++){
                    array.add(nums1[i]);
                }
                break;
            }
            array.add(nums1[index1] < nums2[index2] ? nums1[index1] : nums2[index2]);
            if(nums1[index1] < nums2[index2]){
                if(index1 < size1)
                    index1++;
            }
            else{
                if(index2 < size2) index2++;
            }
        }

        int sizeArray = array.size() / 2;
        if(array.size() % 2 == 0) return (array.get(sizeArray - 1) +         array.get(sizeArray)) / 2.00;
        else return array.get(sizeArray);
    }

•解法二

在考虑题目时间复杂度O(log(m + n))的情况下，我换了一种解法，这种解法也没啥精妙的地方，主要是对中位数的概念理解好了，就容易想到。首先很多时候，我们看到了log一般就要想到二分法。

具体思路，中位数的概念其实可以理解为，将数组整体分为两个部分，一边大于等于中位数，一边小于等于中位数。那么在这道题目中两个有序数组，我们可以将两个数组并排画一条线，这条线能正好划分左右两个部分，而我们的任务就是要找到这条线。可能形容起来比较吃力，话不多说，上图看。

就是为了找到i，j连起来的线，能够正好将两个数组划分成左右两个部分，划分好了之后，只需要记录左边最大的值和右边最小的值，通过这两个值求解中位数就可以了，研究之后你就会发现i和j的关系是

i + j = m - i  + n - j

因为左边部分和右边部分的数量要相等，有了这个之后，我们只要最开始随机确定i（直接在小数组中间取i），然后通过左右移动i（j移动的方向和i相反）找到我们要的那条线。不过一定要小心边界问题，对于边界要进行处理好哦。代码如下

public static double Test4S3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return Test4S3(nums2,nums1); // 保证 m <= n
        }
        int iMin = 0, iMax = m;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && nums2[j-1] > nums1[i]){ // i 需要增大
                iMin = i + 1;
            }
            else if (i != 0 && j != n && nums1[i-1] > nums2[j]) { // i 需要减小
                iMax = i - 1;
            }
            else { // 达到要求，并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { maxLeft = nums2[j-1]; }
                else if (j == 0) { maxLeft = nums1[i-1]; }
                else { maxLeft = Math.max(nums1[i-1], nums2[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) { minRight = nums2[j]; }
                else if (j == n) { minRight = nums1[i]; }
                else { minRight = Math.min(nums2[j], nums1[i]); }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }

•解法三

最激动人心的解法来了，我当时看到这个解法的时候，感叹连连，解法非常的精妙有容易理解，利用第K小数的思想，使用递归二分法进行解决。

具体思路，中位数其实就是第（总长度）/2小的数（奇偶我就不多说了，为了方便我就直接用奇数了），以为两个数组都是有序的，所以我们每次通过循环排除K的一半，直到最后找到K。看图看图，已这个例子为例，我们要找的K是7.

这个时候K/2等于3，然后我们比较两个数组的第三个位置上的数，就可以排除小的那一边的三个数一定不是第K小，然后我们这个时候将排除的数标记。

这个时候因为我们已经排除了3个数，接下来我们只要在新的两个数组中，找到K-3也就是第4小的数就可以了，同样的，将K比较K一半为止的数，重复如此

所以我们采用递归的思路，为了防止数组长度小于 k/2，所以每次比较 min(k/2，len(数组) 对应的数字，把小的那个对应的数组的数字排除，将两个新数组进入递归，并且 k 要减去排除的数字的个数。递归出口就是当 k=1 或者其中一个数字长度是 0 了。直接上代码。

    private static int kMinNum(int start1, int end1, int[] nums1, int start2, int end2, int[] nums2, int k){
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if(len1 > len2) return kMinNum(start2, end2, nums2, start1, end1, nums1, k);
        if(len1 == 0) return nums2[start2 + k - 1];
        if(k == 1) return Math.min(nums1[start1], nums2[start2]);
        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if(nums1[i] > nums2[j]){
            return kMinNum(start1, end1, nums1, j + 1, end2, nums2,k - (j - start2 + 1));
        }else{
            return kMinNum(i + 1, end1, nums1, start2, end2, nums2, k - (i - start1 + 1));
        }
    }

    public static double Test4S1(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        return (kMinNum(0, n - 1, nums1, 0, m - 1, nums2, left) + kMinNum(0, n - 1, nums1, 0, m - 1, nums2, right)) * 0.5;
    }

•结束

第三种解法真的感觉相当的精妙，这种思路很值得去吃透理解。

题目描述：

给定一个未排序的整数数组，找到其中位数。

给出数组[7, 9, 4, 5]，返回 5

解题思路：

利用快排划分的思想，递归处理。

参考代码：

<span style="font-size:18px;">public class Solution {

public int median(int[] nums) {
	return sub(nums, 0, nums.length - 1, (nums.length + 1) / 2);
}
private int sub(int[] nums, int start, int end, int size) {
	int mid = (start + end) / 2;
	int pivot = nums[mid];
	int i = start - 1, j = end + 1;
	for (int k = start; k < j; k++) {
		if (nums[k] < pivot) {
			i++;
			int tmp = nums[i];
			nums[i] = nums[k];
			nums[k] = tmp;
		}
		else if (nums[k] > pivot) {
			j--;
			int tmp = nums[j];
			nums[j] = nums[k];
			nums[k] = tmp;
			k--;
		}
	}
	if (i - start + 1 >= size) {
		return sub(nums, start, i, size);
	}
	else if (j - start >= size) {
		return nums[j - 1];
	}
	else {
		return sub(nums, j, end, size - (j - start));
	}
}
}</span>