DeepSeek LeetCode 2040.两个有序数组的第 K 小乘积 Python3实现

pythonfrom typing import Listimport bisectclass Solution:def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) - int:# 统计乘积 mid 的个数def count(mid: int) - int:cnt 0for a in nums1:if a 0:# a * b mid b floor(mid / a)target mid // acnt bisect.bisect_right(nums2, target)elif a 0:# a * b mid b ceil(mid / a) ceil(-mid / -a)a_pos -atarget (-mid a_pos - 1) // a_pos # 向上取整公式cnt len(nums2) - bisect.bisect_left(nums2, target)else: # a 0if mid 0:cnt len(nums2)return cnt# 答案可能的最小值与最大值四个角乘积的最值cand [nums1[0] * nums2[0],nums1[0] * nums2[-1],nums1[-1] * nums2[0],nums1[-1] * nums2[-1],]left, right min(cand), max(cand)# 二分搜索答案while left right:mid (left right) // 2if count(mid) k:left mid 1else:right midreturn left