4.md

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

中位数，如果数组是奇数，返回中间数。如果是偶数，返回最中间两个数的平均值。

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

思路 1：先合并为一个数组

如何合并数组，并保证时间复杂度在 O(m+n)？

• 使用指针，记录比较位置
• 两个指针，依次比较两个数组的元素大小，小的放入结果数组；其中一个遍历结束时，另一个剩余部分直接全部加入结果数组

nums1 [1, 2]   nums2 [3, 4]     result [1]
i      ^       j	  ^
nums1 [1, 2]   nums2 [3, 4]     result [1, 2]
i         ^    j	  ^

Code

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;
        int[] result = new int[nums1Len + nums2Len];
        if (nums1Len == 0) {
            for (int i = 0; i < nums2Len; i++) {
                result[i] = nums2[i];
            }
        }

        if (nums2Len == 0) {
            for (int i = 0; i < nums1Len; i++) {
                result[i] = nums1[i];
            }
        }
        int i = 0; // 指向 nums1 的指针
        int j = 0; // 指向 nums2 的指针
        // 结束条件为两个数组均遍历完
        while ((i + j) < result.length) {
            // 避免下标溢出
            // 均在范围内时，谁小谁加入结果数组
            if (i < nums1Len && j < nums2Len) {
                if (nums1[i] < nums2[j]) {
                    result[i + j] = nums1[i];
                    i = i + 1;
                } else {
                    result[i + j] = nums2[j];
                    j = j + 1;
                }
            }
            // 其中一个遍历结束时，另一个剩余部分直接全部加入结果数组
            if (i >= nums1Len) {
                result[i + j] = nums2[j];
                j = j + 1;
            } else if (j >= nums2Len) {
                result[i + j] = nums1[i];
                i = i + 1;
            }
            
            if (i < nums1Len && nums1[i] <= nums2[j]) {
                result[i + j] = nums1[i];
                i = i + 1;
            } 
            else if (j < nums2Len && nums2[j] <= nums1[i]) {
                result[i + j] = nums2[j];
                j = j + 1;
            }
        }
        if (result.length % 2 == 1) {
            int mid = (result.length - 1) / 2;
            return result[mid];
        } else {
            int mid1 = result[result.length / 2 - 1];
            int mid2 = result[result.length / 2];
            return (mid1 + mid2) / 2.0;
        }
    }
}

思路 2：不使用额外数组保存

根据中位数的数组下标的得到中位数的值

Code

class Solution {
    private double findMedian(int[] nums) {
        if (nums.length % 2 == 1) {
            return nums[(nums.length - 1) / 2];
        } else {
            int mid1 = nums[nums.length / 2 - 1];
            int mid2 = nums[nums.length / 2];
            return (mid1 + mid2) / 2.0;
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int nums1Len = nums1.length;
        int nums2Len = nums2.length;

        if (nums1Len == 0) {
            return findMedian(nums2);
        }
        if (nums2Len == 0) {
            return findMedian(nums1);
        }
        int sumLen = nums1Len + nums2Len;
        int midIndex1, midIndex2;
        int mid1 = 0, mid2 = 0;
        // 计算「两个中位数」的平均数，为奇数时两个中位数相同
        if (sumLen % 2 == 1) {
            midIndex1 = (sumLen - 1) / 2;
            midIndex2 = midIndex1;
        } else {
            midIndex1 = sumLen / 2 - 1;
            midIndex2 = sumLen / 2;
        }

        int i = 0; // 指向 nums1 的指针
        int j = 0; // 指向 nums2 的指针
        // 结束条件为两个数组均遍历完
        while ((i + j) < sumLen) {
            // 避免下标溢出
            if (i < nums1Len && j < nums2Len) {
                if (nums1[i] < nums2[j]) {
                    if (i + j == midIndex1) {
                        mid1 = nums1[i];
                    }
                    if (i + j == midIndex2) {
                        mid2 = nums1[i];
                    }
                    i = i + 1;
                } else {
                    if (i + j == midIndex1) {
                        mid1 = nums2[j];
                    }
                    if (i + j == midIndex2) {
                        mid2 = nums2[j];
                    }
                    j = j + 1;
                }
            }
            if (i >= nums1Len) {
                if (i + j == midIndex1) {
                    mid1 = nums2[j];
                }
                if (i + j == midIndex2) {
                    mid2 = nums2[j];
                }
                j = j + 1;
            } else if (j >= nums2Len) {
                if (i + j == midIndex1) {
                    mid1 = nums1[i];
                }
                if (i + j == midIndex2) {
                    mid2 = nums1[i];
                }
                i = i + 1;
            }
        }
        return (mid1 + mid2) / 2.0;
    }
}

• 可优化为找到中位数就提前结束
• 可优化 while 块，简化代码

Test

[1,2]
[3,4]

[]
[1]

拓展

面试题

s1 10w 有序
               >    找出两个有序数组中第 10w 个大的数。
s2 10w 有序    

直接查找第 10w 个数，比查找 20w 的中位数更简单一点，合并后，直接取第 10 万个数即可