关于java:LeetCode004寻找两个正序数组的中位数

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

题目形容:给定两个大小别离为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

示例阐明请见LeetCode官网。

起源:力扣(LeetCode)
链接:https://leetcode-cn.com/probl…
著作权归领扣网络所有。商业转载请分割官网受权,非商业转载请注明出处。

解法一:有序数组合并

将2个数组按程序合并到一个大数组外面,2个数组都只会遍历一次。而后在大数组中获取中位数。

解法二:待实现

思考怎么在 工夫复杂度为 O(log (m+n))下实现?

public class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] allNums = new int[nums1.length + nums2.length];
        int i = 0, j = 0, x = 0;
        int num1 = Integer.MAX_VALUE, num2 = Integer.MAX_VALUE;
        for (; i < nums1.length || j < nums2.length; ) {
            if (i < nums1.length) {
                num1 = nums1[i];
            }
            if (j < nums2.length) {
                num2 = nums2[j];
            }
            if (num1 < num2) {
                allNums[x] = num1;
                i++;
            } else {
                allNums[x] = num2;
                j++;
            }
            x++;
            num1 = Integer.MAX_VALUE;
            num2 = Integer.MAX_VALUE;
        }
        int count = nums1.length + nums2.length;
        if (count % 2 == 1) {
            return allNums[count / 2];
        } else {
            return ((double) (allNums[count / 2 - 1] + allNums[count / 2])) / 2;
        }
    }

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

【腾讯云】云产品限时秒杀,爆款1核2G云服务器,首年99元

阿里云限时活动-2核2G-5M带宽-40-100G SSD服务器,特惠价86元/年(原价724元/年,限时99元续购三次),速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

You may also like...

发表评论

邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据