😡 LeetCode 4. 寻找两个正序数组的中位数 [二分查找]

1
class Solution:
2
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
3
    totalLen = m + n
4
    left = (total_len + 1) // 2
5
    right = (total_len + 2) // 2
6

7
  def get_kth(a, b, k):
8

9
    # 通过最短的数组来进行边界判断
10
    if len(a) > len(b):
11
      return get_kth(b, a, k)
12

13
    # 直接返回 b 中第 k 小的元素
14
    if len(a) == 0:
15
      return b[k - 1]
16

17
    i = min(len(a), k // 2)
18
    j = min(len(b), k // 2)
19

20
    # 排除 a 的前半部分
21
    if(a[i - 1] < b[j - 1]):
22
      # 排除了 i 个数，现在找第 k - i 小的
23
      return get_kth(a[i:], b, k - i)
24
    # 大小反过来，或者是相等，都可以调用
25
    # 相等时排除 a 或 b 等价
26
    else:
27
      return get_kth(a, b[j:], k - j)