526互联

『LeetCode』4. 寻找两个正序数组的中位数 Median of Two Sorted Arrays

发布时间 2023-12-23 00:14:09作者: 北岛孤影

『1』合并两个正序数组

我的想法：

先借鉴归并排序的关键步骤将两个数组合并，然后根据数组长度是奇数还是偶数返回中位数。

实现代码：

class Solution {
    // Using the Key Thinking of Merge Sort
    // M is the length of nums1, N is the length of nums2
    // Time Complexity: O(M + N)
    // Space COmplexity: O(M + N)
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int[] nums = new int[m + n];
        if (m == 0) {
            if (n % 2 == 0) return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            else return nums2[n / 2];
        }
        if (n == 0) {
            if (m % 2 == 0) return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
            else return nums1[m / 2];
        }

        int count = 0;
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (nums1[i] <= nums2[j]) nums[count++] = nums1[i++];
            else nums[count++] = nums2[j++];
        }
        while (i < m) nums[count++] = nums1[i++];
        while (j < n) nums[count++] = nums2[j++];

        if (count % 2 == 0) return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        else return nums[count / 2];
    }
}