median_of_two_sorted_arrays

View Source

 1# @leet start
 2class Solution:
 3    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
 4        if len(nums1) > len(nums2):
 5            nums1, nums2 = nums2, nums1
 6
 7        m, n = len(nums1), len(nums2)
 8        l, r = 0, m
 9
10        while l <= r:
11            x_mid = (l + r) // 2
12            y_mid = (m + n + 1) // 2 - x_mid
13
14            max_x = float("-inf") if x_mid == 0 else nums1[x_mid - 1]
15            max_y = float("-inf") if y_mid == 0 else nums2[y_mid - 1]
16            min_x = float("inf") if x_mid == m else nums1[x_mid]
17            min_y = float("inf") if y_mid == n else nums2[y_mid]
18
19            if max_x <= min_y and max_y <= min_x:
20                if (m + n) % 2 == 0:
21                    return (max(max_x, max_y) + min(min_x, min_y)) / 2
22                else:
23                    return max(max_x, max_y)
24            elif max_x > min_y:
25                r = x_mid - 1
26            else:
27                l = x_mid + 1
28
29        return -1.0
30
31
32# @leet end
33
34
35def test():
36    assert 2 + 2 == 4

class Solution: View Source

 3class Solution:
 4    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
 5        if len(nums1) > len(nums2):
 6            nums1, nums2 = nums2, nums1
 7
 8        m, n = len(nums1), len(nums2)
 9        l, r = 0, m
10
11        while l <= r:
12            x_mid = (l + r) // 2
13            y_mid = (m + n + 1) // 2 - x_mid
14
15            max_x = float("-inf") if x_mid == 0 else nums1[x_mid - 1]
16            max_y = float("-inf") if y_mid == 0 else nums2[y_mid - 1]
17            min_x = float("inf") if x_mid == m else nums1[x_mid]
18            min_y = float("inf") if y_mid == n else nums2[y_mid]
19
20            if max_x <= min_y and max_y <= min_x:
21                if (m + n) % 2 == 0:
22                    return (max(max_x, max_y) + min(min_x, min_y)) / 2
23                else:
24                    return max(max_x, max_y)
25            elif max_x > min_y:
26                r = x_mid - 1
27            else:
28                l = x_mid + 1
29
30        return -1.0

def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float: View Source

 4    def findMedianSortedArrays(self, nums1: list[int], nums2: list[int]) -> float:
 5        if len(nums1) > len(nums2):
 6            nums1, nums2 = nums2, nums1
 7
 8        m, n = len(nums1), len(nums2)
 9        l, r = 0, m
10
11        while l <= r:
12            x_mid = (l + r) // 2
13            y_mid = (m + n + 1) // 2 - x_mid
14
15            max_x = float("-inf") if x_mid == 0 else nums1[x_mid - 1]
16            max_y = float("-inf") if y_mid == 0 else nums2[y_mid - 1]
17            min_x = float("inf") if x_mid == m else nums1[x_mid]
18            min_y = float("inf") if y_mid == n else nums2[y_mid]
19
20            if max_x <= min_y and max_y <= min_x:
21                if (m + n) % 2 == 0:
22                    return (max(max_x, max_y) + min(min_x, min_y)) / 2
23                else:
24                    return max(max_x, max_y)
25            elif max_x > min_y:
26                r = x_mid - 1
27            else:
28                l = x_mid + 1
29
30        return -1.0

def test(): View Source

36def test():
37    assert 2 + 2 == 4