LeetCode 每日一题 [4] 求出两个有序数组中位数

LeetCode 求出两个有序数组中位数 [简单]

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

题目分析

解法1：

先合并数组，然后排序，然后找出中位数，返回中位数

解法2：

滑动窗口，求出总长度，然后只需要遍历总长度的一般即可找到答案，因为i两个数组都是有序的。
然后定义左边的数据和右边的数据，此处需要对边界条件进行判断，即左边开始的值不可以小于第一个数组的总长度，然后判断 右边 的大于 数组长度，或者是 第一个数组的某值小于第二个数组的某值，然后执行判断，对应的 索引自增

代码实现

public class LeetCode_04_MedianOfTwoSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        double medianSortedArrays = new LeetCode_04_MedianOfTwoSortedArrays()
                .findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);

    }

    public double findMedianSortedArrays_02(int[] nums1, int[] nums2) {
        if (nums1 == null) {
            throw new RuntimeException("参数1为null;");
        }
        if (nums2 == null) {
            throw new RuntimeException("参数2为null;");
        }
        int m = nums1.length;
        int n = nums2.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;
        for (int i = 0; i <= len / 2; i++) {
            left = right;
            if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
                right = nums1[bStart++];
            } else {
                right = nums2[bStart++];
            }
        }
        if ((len & 1) == 0) {
            return (left + right) / 2.0;
        } else {
            return right;
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1 == null) {
            throw new RuntimeException("参数1为null;");
        }
        if (nums2 == null) {
            throw new RuntimeException("参数2为null;");
        }
        int[] allNumber = new int[nums1.length + nums2.length];
        for (int i = 0; i < nums1.length; i++) {
            allNumber[i] = nums1[i];
        }
        for (int i = 0; i < nums2.length; i++) {
            allNumber[nums1.length + i] = nums2[i];
        }
        Arrays.sort(allNumber);
        if (allNumber.length % 2 == 0) {
            return (allNumber[allNumber.length / 2] + allNumber[allNumber.length / 2 - 1]) / 2.0;
        } else {
            return allNumber[allNumber.length / 2];
        }
    }
}