【Leetcode】668. Kth Smallest Number in Multiplication Table 668. 乘法表中第k小的数
解法
想到是二分搜索了,但是判断函数用了十分慢的方法……= =
其实判断函数很好算
判断函数只需要判断小于等于v的数字的数量是否大于等于k
- 首先,前面的一些行数字比较小,有可能整行都是小于v的,对于第i行,它的数字为
[i*1,i*2,...,i*n]
,那么也就是说,前v//n
行都是整行都小于等于v的 - 然后,对于第i行,小于等于v的数字有
v//i
个,显然,当v<i
的时候,第i行不存在满足条件的数,所以循环从v//n+1
开始,到min(v,m)
结束
class Solution(object):
def findKthNumber(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
if m==1 or n==1:
return k
l,r = 1,m*n
if m>n:
m,n = n,m
def check(v):
res = v//n*n
if res>=k:
return True
for i in xrange(v//n+1,min(v,m)+1):
res += v//i
if res>=k:
return True
return res>=k
while l<r:
mid = (l+r)>>1
# print l,r,mid,t
if check(mid):
r = mid
else:
l = mid+1
return r