【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

巴特西

【leetcode】668. Kth Smallest Number in Multiplication Table

最新文章

热门文章