在两个长度相等的排序数组中找到上中位数

[编程题]在两个长度相等的排序数组中找到上中位数

热度指数：35385 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定两个递增数组arr1和arr2，已知两个数组的长度都为N，求两个数组中所有数的上中位数。

上中位数：假设递增序列长度为n，为第n/2个数

数据范围： $1 \le n \le 10^5$ ， $0 \le arr_1,arr_2 \le 10^9$

要求：时间复杂度 $O(n)$ ，空间复杂度 $O(1)$

进阶：时间复杂度为 $O(logN)$ ，空间复杂度为 $O(1)$

示例1

输入

[1,2,3,4],[3,4,5,6]

输出

说明

总共有8个数，上中位数是第4小的数，所以返回3。

示例2

输入

[0,1,2],[3,4,5]

输出

说明

总共有6个数，那么上中位数是第3小的数，所以返回2

示例3

输入

[1],[2]

输出

备注:

算法知识视频讲解

Python3

水彩笔watercol

class Solution:
    def findMedianinTwoSortedAray(self , arr1: List[int], arr2: List[int]) -> int:
        n = len(arr1)
        k = 0
        index1,index2 = 0,0
        for i in range(0,n):
            if arr1[index1] > arr2[index2]:
                k = arr2[index2]
                index2 += 1
            else:
                k = arr1[index1]
                index1 += 1
        return k

发表于 2024-06-03 22:12:39 回复(0)

Python3