LeetCode: 4. Median of Two Sorted Arrays

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

4. Median of Two Sorted Arrays

LeetCode - Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

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

The median is 2.0

Example 2:

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

The median is (2 + 3)/2 = 2.5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2018-07-01
 */
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
    if (isEmpty(nums1) && isEmpty(nums2)) {
        return 0;
    }
    if (isEmpty(nums1)) {
        return singleArray(nums2);
    }
    if (isEmpty(nums2)) {
        return singleArray(nums1);
    }

    int length = nums1.length + nums2.length;
    boolean isOdd = (length & 1) == 1;
    int i1 = 0;
    int i2 = 0;
    int min = nums1[0] < nums2[0] ? nums1[0] : nums2[0];
    int temp = min;
    int last = min;
    int now = min;
    for (int i = 0; i < length; i++) {
        if (i1 < nums1.length && i2 < nums2.length) {
            if (nums1[i1] <= nums2[i2]) {
                temp = nums1[i1];
                i1++;
            } else {
                temp = nums2[i2];
                i2++;
            }
        } else if (i1 < nums1.length) {
            temp = nums1[i1];
            i1++;
        } else {
            temp = nums2[i2];
            i2++;
        }

        if (i > 0) {
            last = now;
            now = temp;
        }

        if (length / 2 == i) {
            if (isOdd) {
                return now;
            } else {
                return ((double) (last + now)) / 2.0;
            }
        }
    }
    return 0;
}

private static boolean isEmpty(int[] nums) {
    return nums == null || nums.length == 0;
}

public static double findMedianSortedArraysBest(int[] nums1, int[] nums2) {
    // TODO
    return 0;
}

private static double singleArray(int[] nums2) {
    boolean isOdd = (nums2.length & 1) == 1;
    if (isOdd) {
        return nums2[nums2.length / 2];
    } else {
        return (nums2[nums2.length / 2 - 1] + nums2[nums2.length / 2]) / 2.0;
    }
}