x

Median of Two Sorted Arrays

Leetcode #4 | Hard | Бин. поиск | Математика

Идея

Big-O

  • Время O(log(min(n,m)))
  • Память O(1)

Код

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int halfLen = (m+n+1) / 2;

        int l = -1;
        int r = m+1;

        while (r-l > 1) {
            int i = (l+r)/2;
            int j = halfLen - i;

            int Aleft = (i==0) ? Integer.MIN_VALUE : nums1[i-1];
            int Bright = (j == n) ? Integer.MAX_VALUE : nums2[j];

            if (Aleft > Bright) {
                r = i;
            } else {
                l = i;
            }
        }

        int i = l;
        int j = halfLen - i;

        int Aleft  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int Aright = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int Bleft  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int Bright = (j == n) ? Integer.MAX_VALUE : nums2[j];

        if ((m + n) % 2 == 1) {
            return Math.max(Aleft, Bleft);
        } else {
            return (Math.max(Aleft, Bleft) + Math.min(Aright, Bright)) / 2.0;
        }
    }
}
Left-click: follow link, Right-click: select node, Scroll: zoom
x