无标题无名氏No.65945146 只看PO
2025-04-28(一)08:18:47 ID:1th3CTn
各位大佬好, 本肥刚刚开始接触力扣, 为什么这道题运行能通过但是提交一直显示超过时间限制啊? 请各位大佬赐教!
我的解法如下, 我的这个解法时间复杂度是O(log(min(m,n)))
------------------------------------------------------------
题目: 给定两个大小分别为m和n的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数 。
算法的时间复杂度应该为
O(log(m + n)) 。
示例1：
输入：nums1 = [1, 3], nums2 = 2[0,2]
输出：2.00000
解释：合并数组 = [1, 2, 3] ，中位数 2
示例2：
输入：nums1 = [1, 2], nums2 = [3, 4]
输出：2.50000
解释：合并数组 = [1, 2, 3, 4] ，中位数(2 + 3) / 2 = 2.5
------------------------------------------------------------
我的解法:
class Solution:
def findMedianSortedArrays(self, nums1, nums2) -> float:
if len(nums1) > len(nums2):
return self.findMedianSortedArrays(nums2, nums1)
total = len(nums1) + len(nums2)
if total % 2 == 0:
is_even_total = True
else:
is_even_total = False
list1_with_sentinel = [float('-inf')] + nums1 + [float('inf')]
list2_with_sentinel = [float('-inf')] + nums2 + [float('inf')]
list1_left = 0
list1_right = len(list1_with_sentinel) - 1
while True:
list1_mid = (list1_left + list1_right) // 2
list2_ptr = total // 2 - list1_mid
list1_current_item = list1_with_sentinel[list1_mid]
list1_next_item = list1_with_sentinel[list1_mid + 1]
list2_current_item = list2_with_sentinel[list2_ptr]
list2_next_item = list2_with_sentinel[list2_ptr + 1]
if list1_current_item <= list2_next_item and list2_current_item <= list1_next_item:
if is_even_total:
left_part_max = max(list1_current_item, list2_current_item)
right_part_min = min(list1_next_item, list2_next_item)
median = (left_part_max + right_part_min) / 2
else:
right_part_min = min(list1_next_item, list2_next_item)
median = right_part_min
break
if list1_next_item < list2_current_item:
list1_left = list1_mid
if list2_next_item < list1_current_item:
list1_right = list2_ptr
return median