0004 - Median of Two Sorted Arrays

import sys
from typing import List


class Solution(object):
    def findMedianSortedArrays(self, nums_list_1: List[int], nums_list_2: List[int]) -> float:
        # https://github.com/mission-peace/interview/blob/master/src/com/interview/binarysearch/MedianOfTwoSortedArrayOfDifferentLength.java
        # https://discuss.leetcode.com/topic/4996/share-my-o-log-min-m-n-solution-with-explanation
        # https://discuss.leetcode.com/topic/16797/very-concise-o-log-min-m-n-iterative-solution-with-detailed-explanation
        # https://books.halfrost.com/leetcode/ChapterFour/0001~0099/0004.Median-of-Two-Sorted-Arrays/
        # 「数字清单 1」数量
        nums_list_1_length = len(nums_list_1)
        # 「数字清单 2」数量
        nums_list_2_length = len(nums_list_2)

        if nums_list_1_length > nums_list_2_length:
            # 若「数字清单 1」数量大于「数字清单 2」，将交换数字清单顺序，将小的优先传入
            return self.findMedianSortedArrays(nums_list_2, nums_list_1)

        # 「数字清单 1」左侧检查位置（从第一个开始往右检查）
        nums_list_1_left_index = 0
        # 「数字清单 1」右侧检查位置（从最后一个开始往左检查）
        nums_list_1_right_index = nums_list_1_length
        # 所有数字中位数可能位置，全部长度+1，bit 往右位移除 2
        all_nums_list_divide_position = (nums_list_1_length + nums_list_2_length + 1) >> 1
        # 「数字清单 1」中位数位置
        nums_list_1_median_partition_index = 0
        # 「数字清单 2」中位数位置
        nums_list_2_median_partition_index = 0

        # 找寻中位数位置
        while nums_list_1_left_index <= nums_list_1_right_index:
            # 「数字清单 1」左侧检查位置小于右侧位置，继续检查
            # 「数字清单 1」中位数检查拆分位置 = 目前左方最小数字位置 + 右方剩馀数字取中位数 bit 往右位移除 2
            nums_list_1_median_partition_index: int = nums_list_1_left_index + (
                    (nums_list_1_right_index - nums_list_1_left_index) >> 1)
            # 「数字清单 2」中位数检查拆分位置 = 所有数字中位数可能位置 - 数字清单 1 中位数位置
            nums_list_2_median_partition_index: int = all_nums_list_divide_position - nums_list_1_median_partition_index

            if nums_list_1_median_partition_index > 0 and nums_list_1[nums_list_1_median_partition_index - 1] > \
                    nums_list_2[nums_list_2_median_partition_index]:
                # 「数字清单 1」中位数位置不是第一个数字，且有资料
                # 「数字清单 1」中位数左侧数字比「数字清单 2」右侧中位数还大（排序过的数字左侧应比右侧小）
                # 表示整个数字列表的中位数在「数字清单 1」目前中位数之前
                # 「数字清单 1」右方数字索引往左侧移动，找「数字清单 1」中位数前面小一点的数字
                nums_list_1_right_index = nums_list_1_median_partition_index - 1
            elif nums_list_1_median_partition_index != nums_list_1_length and nums_list_1[
                nums_list_1_median_partition_index] < nums_list_2[nums_list_2_median_partition_index - 1]:
                # 「数字清单 1」中位数位置不是最后一个数字，且有资料
                # 「数字清单 1」中位数右侧数字比「数字清单 2」左侧中位数还小（排序过的数字右侧应比左侧大）
                # 「数字清单 1」中位数位置数字 比 「数字清单 2」中位数位位置的前一个数字还小
                # 「数字清单 1」左方数字索引往右侧移动，找「数字清单 1」中位数后面大一点的数字
                nums_list_1_left_index = nums_list_1_median_partition_index + 1
            else:
                # 无法再划分左右侧中位数位置
                break

        # === 找出中位数 ===
        # 中位数
        median_num: float = 0.0
        # 左侧中位数
        median_num_left: int = 0
        # 右侧中位数
        median_num_right: int = 0

        if nums_list_1_median_partition_index == 0:
            # 「数字清单 1」中位数位置为移动到第一个数字，或是没有数字 => 「数字清单 1」左侧都没有资料
            # 中位数左侧数字 = 「数字清单 2」 左侧第一个数字」
            median_num_left = nums_list_2[nums_list_2_median_partition_index - 1]
        elif nums_list_2_median_partition_index == 0:
            # 「数字清单 2」中位数位置移动到第一个数字，表示数字只有一个，或是没有数字 => 「数字清单 2」左侧都没有资料
            # 中位数左侧数字 = 「数字清单 1」 左侧第一个数字」
            median_num_left = nums_list_1[nums_list_1_median_partition_index - 1]
        else:
            # 「数字清单 1」与「数字清单 2」有超过一个数字，有自己的中位数，取两个左侧中位数最大的那一个
            # 左侧的数字比右侧小，所以要找比较大的数字才会接近右侧数字
            median_num_left = max(nums_list_1[nums_list_1_median_partition_index - 1],
                                  nums_list_2[nums_list_2_median_partition_index - 1])


        if (nums_list_1_length + nums_list_2_length) & 1 == 1:
            # 若数字总数量为奇数，直接回传中位数数字
            median_num = float(median_num_left)
            return median_num

        # 若数字总数量为偶数，取得中位数右侧最小数值
        if nums_list_1_median_partition_index == nums_list_1_length:
            # 「数字清单 1」没有数字，或者索引超出范围 => 「数字清单 1」右侧都没有资料，使用「数字清单 2」右侧资料
            median_num_right = nums_list_2[nums_list_2_median_partition_index]
        elif nums_list_2_median_partition_index == nums_list_2_length:
            # 「数字清单 2」没有数字，或者索引超出范围 => 「数字清单 2」右侧都没有资料，使用「数字清单 1」右侧资料
            median_num_right = nums_list_1[nums_list_1_median_partition_index]
        else:
            # 「数字清单 1」与「数字清单 2」有超过一个数字，有自己的中位数，取两个右侧中位数最小的那一个
            median_num_right = min(nums_list_1[nums_list_1_median_partition_index],
                                   nums_list_2[nums_list_2_median_partition_index])

        # 计算中位数左右平均
        median_num = float((median_num_left + median_num_right) / 2.0)

        return median_num


if __name__ == '__main__':
    # begin
    s = Solution()
    print(s.findMedianSortedArrays([1], [2, 3, 4, 5, 6]))
    print(s.findMedianSortedArrays([4], [1, 2, 3, 5, 6]))
    print(s.findMedianSortedArrays([], [1, 2, 3, 5, 6]))