唉
有想到binary search 但我还是偷看了一下答案
现在连写binary search也要想半天
我又郁郁了
def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) ->
int:
def count(x):
# number of products which are less than or equal to x
total_cnt = 0
for num1 in nums1:
if num1>0:
total_cnt += bisect_right(nums2, x/num1)
elif num1==0:
total_cnt += len(nums2) if x>=0 else 0
else:
total_cnt += (len(nums2)-bisect_left(nums2, x/num1))
return total_cnt
l, r = -10**10, 10**10
while l<r:
mid = (l+r)//2
if count(mid)<k:
l = mid+1
else:
r = mid
return l