「リートコード - 4. Median of Two Sorted Arrays」

发表于 | 分类于

ジャバソリューション

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length, m = nums2.length;
        if (n > m) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int left = (n+m+1)/2;
        int u = 0, v = n;
        while (u < v) {
            int mid = (u+v+1)/2;
            if (nums1[mid-1] < nums2[left-mid]) {
                u = mid;
            } else {
                v = mid - 1;
            }
        }
        if ((n + m) % 2 == 1) {
            return u == 0 ? nums2[left-u-1] : left - u == 0 ? nums1[u-1] : Math.max(nums1[u-1], nums2[left-u-1]);
        } else {
            double x = u == 0 ? nums2[left-u-1] : left - u == 0 ? nums1[u-1] : Math.max(nums1[u-1], nums2[left-u-1]);
            double y = u == n ? nums2[left-u] : left - u == m ? nums1[u] : Math.min(nums1[u], nums2[left-u]);
            return (x + y) / 2;
        }
    }
}

没想到写了不知道多少遍还是翻车，写了个程序一直调结果还是错，最后看了题解又恍然大悟。