P8 寻找两个有序数组的中位数 LeetCode4

题解后补。

题目

---

解题

伪代码描述（推荐）

---

思路及源码

Java解法一

思想：先将两个数组合并，归并排序。根据奇数，还是偶数，返回中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m + n]; 
        // nums1为空
        if (m == 0) {
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            } else {
                return nums2[n / 2];
            }
        }
		
        // nums为空
        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;
        // nums数组未合并完
        while (count != (m + n)) {
            // nums1合并完，直接将nums2剩余部分复制到nums后
            if (i == m) {
                while ( j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }
			
            // nums1、nums2逐一复制到nums中
            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }
        }
		
        // 按奇偶返回中位数
        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[ count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }
}

时间复杂度：遍历全部数组，O（m + n）

空间复杂度：开辟了一个数组，保存合并后的两个数组，O（m + n）

本文作者： Yao Zhu
发布时间： 2019-12-16
最后更新： 2019-12-17
本文链接： https://juoyo.github.io/posts/599b393a.html
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝

微信