LeetCode刷题笔记-4. 寻找两个正序数组的中位数

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

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5

示例3：

输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000

示例 4：

输入：nums1 = [], nums2 = [1]
输出：1.00000

示例 5：

输入：nums1 = [2], nums2 = []
输出：2.00000

我的解法

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] array = new int[nums1.length + nums2.length];
    int j = 0;
    for (int i = 0; i < nums1.length + nums2.length; i++) {
        if (i <= nums1.length - 1) {
            array[i] = nums1[i];
        } else {
            array[i] = nums2[j++];
        }
    }

    Arrays.sort(array);

    if (array.length % 2 == 0) {
        // 偶数
        int consult = array.length / 2;
        return (array[consult] + array[consult - 1]) / 2.0;
    } else {
        // 奇数
        int consult = (array.length + 1) / 2;
        return array[consult - 1];
    }
}

复杂度分析

• 时间复杂度：O(m + n) ，Arrays.sort(array) 这类使用了jdk的排序，好像是用的快排，这里可能也要加上这里的时间复杂度nlogn
• 空间复杂度：O(m+n)

不使用Arrays.sort方法

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] array = new int[nums1.length + nums2.length];
        int j = 0, k = 0, i = 0;
        boolean num1End = false;
        boolean num2End = false;


        // 定义两个索引 j,k 分别指向两个数组，每次比较两个数组最小的放入最终结果数组，并移动索引,大的一方不移动
        // 当某一方移动到结尾时，将另一边数组剩余的数据直接放到尾部
        while (i < nums1.length + nums2.length && nums1.length != 0 && nums2.length !=0) {
            if (num1End || num2End) {
                if (num1End) {
                    array[i++] = nums2[k++];
                } else {
                    array[i++] = nums1[j++];
                }
                continue;
            }

            if (nums1[j] < nums2[k]) {
                array[i++] = nums1[j];
                if (j != nums1.length - 1) {
                    j++;
                } else {
                    num1End = true;
                }
            } else {
                array[i++] = nums2[k];
                if (k != nums2.length - 1) {
                    k++;
                } else {
                    num2End = true;
                }
            }
        }

        //判断空数组
        if (nums1.length == 0){
            array = nums2;
        }
        if (nums2.length == 0){
            array = nums1;
        }

        if (array.length % 2 == 0) {
            // 偶数
            int consult = array.length / 2;
            return (array[consult] + array[consult - 1]) / 2.0;
        } else {
            // 奇数
            int consult = (array.length + 1) / 2;
            return array[consult - 1];
        }
    }

复杂度分析

• 时间复杂度：O(m + n)
• 空间复杂度：O(m+n)

上面两个解法，时间复杂度都不满足题目要求的O(log (m+n)) ，官方提出的解法是二分法，有点烧脑

后续更新官方解法...