算法-数组中位数/第k小数

最近打算把家里装修一下，上周都在忙搬家的事情，说好的每周一更鸽了一周，这周续上。之前几年除了面试外几乎很少刷算法题，二月底和几个朋友开始了个人周报制度，在周计划中也加入了每日一道算法题。截止到目前还是刷了不少题，逐渐找到了算法的乐趣，开了一个分类来记录这些题目和解决办法。

题目

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数 。

1.合并数组

一开始看到这个题的思路很简单，合并两个数组，然后找到中位数就行了。不过因为最近面试了很多算法，我并没有真的去搞一条数组来合并这两个数组，那样的话内存的消耗就太高了。

2.两个指针

思路和合并数组其实是完全一样的，只是稍微思考一下就可以想到我们并不需要真的去合并两条数组，如果设置两个指针，分别在数组a和数组b上移动，根据正序的特点可以很容易的像处理一条数组一样来进行遍历。这样就优化了解法1中的空间复杂度变为O(1)。而且说实话这个解法很容易想到，通过代码实现的难度也比较低，如果面试的话我可能一开始还是会选用这种方式吧，因为第三种我一开始写了好几次都没过…

3.第k小数

这道题要求时间复杂度为O(log(m+n))，而第2种解法虽然优化了空间复杂度，但是时间复杂度依然是O(m+n)

这个才是本文要记录的解法，事实上数组中位数这个题目本质是从正序数组中找第k小数。只不过k=( m+n)/2 而已。

这个解法的基本逻辑是：沿用1和2的思路，先看作一个大数组，那么这个大数组的第K个数之前的所有数一定都比k位置上的数小。（这个不理解就不用往后看了）

A = [1,3,5,7,9]
B = [2,4,6,8,10]

假设K=6，我们可以从数组a上取第 k/2 位置的数和数组b上第k/2的数来进行比较，较小的那个值一定小于我们要找的第k个数，在这个例子中k/2 == 3：

第一次对比

// 注意：我们要取的是第三个位置，而数组是从0开始的，所以索引应该是2，这个写代码的时候也要注意
A[2] == 5
B[2] == 6
// 显然5小于6
A[2] < B[2]

A数组前三个数都应该被扔掉

A = [7, 9]
B = [2,4,6,8,10]

在我们继续往下之前，我们思考一个问题，为什么 A[2] < B[2] ，就可以断定 A数组中的前三个数字都可以安全的被扔掉呢？我们试着来证伪这个结论：

还是以这个例子来看，假如我们要找的第6小的那个数在数组A中：

那么可以得出数组A的第3个位置就是大数组的第六个位置
也就是说，大数组的前5个位置中一定有3个数在B数组中
并且一定是B数组的前三个数。
既然这样的话，那B数组的第3个数一定是小于A数组的第3个数的，对吧？（k位置之前的数一定都比k位置的数小）
而事实是 A[2] < B[2]，所以这个假设是不成立的！

因此可以判定数组A中的前3个数都一定比K小。

第二次对比

第一次对比后，我们之前要找的第 6 个位置，现在就变成了第3个位置，即 k = 3。k/2 = 1

A = [7, 9]
B = [2,4,6,8,10]
A[0] = 7// 原始数组中其实是A[3]
B[0] = 2
// 7>2
A[0] > B[0]

扔掉B数组的第一个数

第三次对比

k = 2， k/2 = 1

A = [7, 9]
B = [4, 6, 8, 10]
A[0] = 7// 原始数组中其实是A[3]
B[0] = 4
// 7>4
A[0] > B[0]

第四次对比

k = 1，当k=1 就意味着我们在找这个大数组的第一个数对吧？hold up， hold up！注意了，这里需要取更小的那个数字，不再是和前面一样扔掉小的数字了

A[0] = 7
B[0] = 6
显然我们的答案是6

所以K=1是这个解法一个重要的递归完结条件。

时间复杂度

发现了么，这种做法其实就是二分查找啊，这不就完成了 O(log(m+n)) 的时间复杂度要求了么。

问题和边界条件

假如一条数组的长度不够k/2怎么办？

用这条数组的最后一个数字来比较就好了，如果刚好又更小，那就可以直接在另一条数组上找到答案了
假如数组A 和数组B k/2 上的值相同怎么办？

随便扔一个，一样的，不信你去证伪
为什么是 k/2?

…因为题目给的是两条数组，如果是3条那就是k/3
如果两个数组加起来的长度是偶数怎么办？

那就是求第K 和第K+1 个数

4.Show me ur code

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val totalSize = nums1.size + nums2.size
      // 区分奇偶
        if (totalSize % 2 == 0) {
            return (findMedianSortedExec(nums1, nums2, 0, 0, totalSize / 2 + 1) + findMedianSortedExec(nums1, nums2, 0, 0, totalSize / 2)) / 2
        }
        return findMedianSortedExec(nums1, nums2, 0, 0, totalSize / 2 + 1)
    }
    fun findMedianSortedExec(nums1: IntArray, nums2: IntArray, nums1Start: Int, nums2Start: Int, medianPos: Int): Double {
      	// 保证数组1的长度始终是较短的那个，这样可以减少边界
        if (nums1.size - nums1Start > nums2.size - nums2Start) {
            return findMedianSortedArraysBetter(nums2, nums1, nums2Start, nums1Start, medianPos)
        }
      // 计算当前数组的长度（我们不是真正的去操作数组扔掉数据，而是通过计算位置来实现）
        val len1 = nums1.size - nums1Start
        val len2 = nums2.size - nums2Start
      
      // 当数组1的长度已经为0了，直接从数组2中获取结果
        if (len1 <= 0) {
            return nums2[nums2Start + medianPos - 1].toDouble()
        }
      // k == 1，结束递归
        if (medianPos == 1) {
            // 可以给出中位数了
            return Math.min(nums1[nums1Start], nums2[nums2Start]).toDouble()
        }
      // 获取两个数组k/2位置的值
        var comparePos1 = nums1Start + Math.min(len1, medianPos / 2) - 1
        var comparePos2 = nums2Start + Math.min(len2, medianPos / 2) - 1
        
      // 比较大小，扔掉较小的那一边
        val newMedianPos: Int
        if (nums1[comparePos1] > nums2[comparePos2]) {
            newMedianPos = medianPos - (comparePos2 - nums2Start) - 1
            comparePos1 = nums1Start
            comparePos2 += 1
        } else {
            newMedianPos = medianPos - (comparePos1 - nums1Start) - 1
            comparePos2 = nums2Start
            comparePos1 += 1
        }
        //递归求解
        return findMedianSortedArraysBetter(nums1, nums2, comparePos1, comparePos2, newMedianPos)
    }
}

5.思考

当遇到时间复杂度为O(log (m+n))，基本就可以确定是二分查找的思路
多次算法题我发现一定要学会去证伪自己的思路，只有当自己的思路是不会被证伪的时候才能确定它的正确性，否则在实现过程中会发现有无数的边界条件要处理
对于边界的处理，首先当然是要思考边界条件，同时要学会去简化代码中对边界的处理，这道题我一开始写代码的时候发现要处理的边界太多太多了，因为我并没有收敛好代码，导致无数测试因为边界问题falied。
事实上代码越少反而会越健壮，因此实现的时候也要仔细思考代码结构和执行过程