Re: [閒聊] 每日leetcode
看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間5月前 (2025/06/25 22:44)推噓1(1推 0噓 0→)留言1則, 1人參與討論串1455/1548 (看更多)
唉
有想到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
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 220.132.58.28 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1750862662.A.E0A.html
※ 編輯: DJYOSHITAKA (220.132.58.28 臺灣), 06/25/2025 22:45:17
推
06/25 22:51,
5月前
, 1F
06/25 22:51, 1F
討論串 (同標題文章)
完整討論串 (本文為第 1455 之 1548 篇)：