LeetCode题解 4.寻找两个正序数组的中位数

这道题看官方题解捋了一天，终于整明白了，特此记录一下以免忘球了😄。

学习算法的道路还是很漫长呀...

LeetCode 4.寻找两个正序数组的中位数

解题思路

首先读题，题目的意思是找到两个正序数组的中位数(转为浮点数)。根据题目可总结出以下条件：

• 两个正序数组至少有一个不为空
• 两个数组长度之和为奇数的时候，中位数只有一个，直接返回中位数；两个数组长度之和为偶数的时候，中位数有两个，返回两个中位数的平均值

官方视频题解使用二分查找法，找一条两个数组的分割线，中位数与分割线两侧的元素有关；

则这条分割线需要满足如下条件：

• 条件1： 两个数组用一条分割线分割成两部分；如果两个数组长度之和为奇数，则分割线左边的元素数量比右边元素数量多一个；如果两个数组长度之和为偶数，则分割线左边的元素数量和右边元素数量相同；

• 条件2： 分割线左边所有元素的值都要小于等于右边元素所有的值，并且保证交叉小于等于成立；

• 在满足1和2条件的前提下，如果两个数组长度之和为奇数，分割线紧邻两侧左边的最大值即为中位数；如果两个数组长度之和为偶数，分割线紧邻两侧左边的最大值为其中一个中位数(该中位数也是左边所有元素的最大值)，分割线紧邻两侧右边的最小值为另外一个中位数(该中位数也是右边所有元素的最小值)；

两个条件的计算方法：

条件1的计算方法：
计算分割线左边元素个数，假设分割线左边元素个数为sizeLeft，数组1元素个数为m，数组2元素个数为n
当两个数组长度之和为奇数的时候，因为我们提前约定好分割线左边的元素数量比右边元素数量多一个，所以计算公式上取整为 int sizeLeft = (m + n + 1) / 2；举例m为2，n为3，两者之和再加一的平均值为3，满足分割线左边的元素数量比右边元素数量多一个的约定。
当两个数组长度之和为偶数的时候，所以计算公式为int sizeLeft = (m + n) / 2；但是如果这样做我们需要分别对数组的奇偶性进行判断。由于Java声明的int类型，除法除不尽取整默认是上取整，所以计算公式也可以为 int sizeLeft = (m + n + 1) / 2；举例m为2，n为4，两者之和平均值为3，如果两者之和加一的话，Java中7/2上取整也是3；这样公式一致我们就不用对数组的奇偶性进行判断了
假设该分割线在第一个数组中位置为i，i为第一个数组左边元素的个数；在第二个数组中位置为j，j为第二个数组左边元素的个数；i + j = sizeLeft = (m + n + 1) / 2

条件2的计算方法：
分割线左边所有元素的值都要小于等于右边元素所有的值比较好理解；不满足交叉小于等于关系的时候就要调整分割线位置，保证交叉小于等于成立的意思是：

• 第一个数组在分割线左边最大值要小于等于第二个数组在分割线右边的最小值
  如果不满足1>，则说明第一个数组分割线左边的元素值太大了，分割线需要在第一个数组中的位置左移
• 第二个数组在分割线左边的最大值要小于等于第一个数组在分割线右边最小值
  如果不满足2>，则说明第一个数组分割线右边的元素值太小了，分割线需要在第一个数组中的位置右移
• • 考虑条件2计算时的极端情况：
    当两个数组长度不一致时，较短数组在分割线的左边或者右边没有元素，会出现下标越界的情况；所以应该在较短的数组上确定中间数分割线位置
    当两个数组长度一致时，第一个数组在分割线的右边没有元素，第二个数组在分割线的左边没有元素，或者一个数组在分割线的左边没有元素，第二个数组在分割线的右边没有元素，也会出现下标越界的情况；

最终算法代码和注释

class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //当两个数组长度不一致时，较短数组在分割线的左边或者右边没有元素，会出现下标越界的情况；所以应该在较短的数组上确定中间数分割线位置；经过卫语句后如果数组长度不一致，最短数组应为nums1。
        if(m > n) {
            int temp[] = nums1;
            nums1 = nums2;
            nums2 = temp;
            m = nums1.length;
            n = nums2.length;
        }
        //计算分割线左边元素个数
        int sizeLeft = (m + n + 1) / 2;
        //在较短的数组nums1中的[0, m]区间内确定恰当的分割线位置。假设该分割线在第一个数组中位置为i，在第二个数组中位置为j，i + j = sizeLeft；保证交叉小于等于成立则nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]；i - 1 或者 j - 1 代表在分割线的左边元素下标
        int left = 0;
        int right = m;
        //二分法寻找分割线，退出循环时left == right成立
        while(left < right) {
            //i既是分割线在第一个数组中位置，也是第一个数组左边元素的个数；此处上取整的原因是后面有left = i，向上取整意味着此处i严格大于0，所以后面的nums[i - 1]也不会下标越界
            int i = left + (right - left + 1) / 2;
            //j既是分割线在第二个数组中位置，也是第二个数组左边元素的个数；所以j = sizeLeft - i;
            int j = sizeLeft - i;
            //当不保证交叉小于等于成立时，即对nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]取反，由于中间为&&符号，则nums1[i - 1] > nums2[j]时交叉小于等于必不成立，可以不考虑&&后的条件
            if(nums1[i - 1] > nums2[j]) {
                //第一个数组分割线左边的元素值太大了，分割线需要在第一个数组中的位置左移，搜索区间缩小为[left, i - 1]
                right = i - 1;
            } else {
                left = i;
            }
        }
        //循环完后确定的较短数组的分割线位置
        int i = left;
        //循环完后确定的另一个数组的分割线位置
        int j = sizeLeft - i;
        //第一个数组在分割线左边最大值元素，当 i 等于 0 时nums1[i - 1]下标越界，所以将第一个数组左边最大值元素设置为整型的最小值，防止比较分割线紧邻两侧左边最大值的时候被选中
        int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
        //第一个数组在分割线右边最小值元素，当 i 等于 m 时nums1[m]下标越界，所以将第一个数组右边最小值元素设置为整型的最大值，防止比较分割线紧邻两侧右边最小值的时候被选中
        int nums1RightMin = i == m ?  Integer.MAX_VALUE : nums1[i];
        //第二个数组在分割线左边最大值元素，当 j 等于 0 时nums2[j - 1]下标越界，所以将第二个数组左边最大值元素设置为整型的最小值，防止比较比较分割线紧邻两侧左边最大值的时候被选中
        int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
        //第二个数组在分割线右边最小值元素，当 j 等于 n 时nums2[n]下标越界，所以将第二个数组右边最小值元素设置为整型的最大值，防止比较分割线紧邻两侧右边最小值的时候被选中
        int nums2RightMin = j == n ? Integer.MAX_VALUE : nums2[j];
        //数组之和取余，余数为1说明数组之和是奇数
        if( ((m + n) % 2) == 1 ) {
            //两个数组长度之和为奇数，分割线紧邻两侧左边的最大值即为中位数；
            return Math.max(nums1LeftMax, nums2LeftMax);
        } else {
            //两个数组长度之和为偶数，分割线紧邻两侧左边的最大值为其中一个中位数(该中位数也是左边所有元素的最大值)，分割线紧邻两侧右边的最小值为另外一个中位数(该中位数也是右边所有元素的最小值)，两数求和取平均值
            return (double) ((Math.max(nums1LeftMax, nums2LeftMax)) + (Math.min(nums1RightMin, nums2RightMin))) / 2;
        }
    }
}