【leetcode】668. Kth Smallest Number in Multiplication Table

题目如下:

【leetcode】668. Kth Smallest Number in Multiplication Table

解题思路:几乎和【leetcode】719. Find K-th Smallest Pair Distance 的方法一样。只不过一个是减法一个是乘法,还有一点区别是【leetcode】719. Find K-th Smallest Pair Distance中i-j和j-i只算一个元素,而本题中i*j与j*i算两个元素。

代码如下:

class Solution(object):
def findKthNumber(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
low,high = 1, m*n while low <= high:
mid = (low + high) / 2
less,equal = 0,0
for i in range(1,min(mid+1,m+1)):
less += min(mid/i,n)
if mid/i <= n and mid % i == 0:
equal += 1
less -= 1 if less >= k:
high = mid - 1
elif less + equal < k:
low = mid + 1
elif less == k and equal == 0:
high = mid - 1
else:
break
return mid
上一篇:【linux草鞋应用编程系列】_4_ 应用程序多线程


下一篇:Linux多线程编程(不限Linux)【转】