https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

题目

给定两个大小为 m 和 n 的有序数组nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

概念

中位数的概念:
对于有限的数集,可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个,通常取最中间的两个数值的平均数作为中位数。

复杂度 log(m+n),参考文章:
https://github.com/xitu/gold-miner/blob/master/TODO/what-does-the-time-complexity-o-log-n-actually-mean.md

思路

  • 两个有序数组
  • 中位数
  • 复杂度O(log(m + n))

解题

第一次提交

臭不要脸的提交。本着试一试的态度提交。这个答案显然不符合负责度的要求。竟然是通过。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        List<Integer> nums_a = new ArrayList<>();
        List<Integer> nums_b = new ArrayList<>();
        for (int i = 0; i < nums1.length; i++) {
            nums_a.add(nums1[i]);
        }
        for (int i = 0; i < nums2.length; i++) {
            nums_b.add(nums2[i]);
        }
        nums_a.addAll(nums_b);
        Collections.sort(nums_a);
        if (nums_a.size() % 2 == 0) {
            int mid = nums_a.size() / 2;
            return (nums_a.get(mid) + nums_a.get(mid - 1)) / 2.0f;
        } else {
            int mid = (nums_a.size() - 1) / 2;
            return nums_a.get(mid);
        }
    }
}

第二次提交

关于这段代码,看详细题解,得多看几遍。
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        if (n > m)  {
            return findMedianSortedArrays(nums2, nums1);
        }
        int L1 = 0, L2 = 0, R1 = 0, R2 = 0, c1, c2, lo = 0, hi = 2 * n;  
        while (lo <= hi)   
        {
            c1 = (lo + hi) / 2;  
            c2 = m + n - c1;
            L1 = (c1 == 0) ? Integer.MIN_VALUE : nums1[(c1 - 1) / 2];   //map to original element
            R1 = (c1 == 2 * n) ? Integer.MAX_VALUE : nums1[c1 / 2];
            L2 = (c2 == 0) ? Integer.MIN_VALUE : nums2[(c2 - 1) / 2];
            R2 = (c2 == 2 * m) ? Integer.MAX_VALUE : nums2[c2 / 2];

            if (L1 > R2) {
                hi = c1 - 1;
            } else if (L2 > R1) {
                lo = c1 + 1;
            } else {
                break;
            }
        }
        return (Math.max(L1, L2) + Math.min(R1, R2)) / 2.0;
    }
}

总结

  • 思考未果可看题解,前提是必须先思考
  • 概念的深入理解很重要

results matching ""

    No results matching ""