乐趣区

关于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));
    }
}
退出移动版