[LeetCode] Challenge log 668

Posted on |
668. Kth Smallest Number in Multiplication Table

Similar to #378: http://localhost:4000/2018/06/21/LeetCode-Challenge-log-378/, except now we can count how many smaller faster in O(n) time! There is also two tricks to achieve 99% beaten:

  1. Switch m and n if m > n. So it can count faster
  2. Do not use build-in min() but if statement. Too many function calls slows down the speed.

Nearly every one have used the Multiplication Table. But could you find out the k-th smallest number quickly from the multiplication table?

Given the height m and the length n of a m * n Multiplication Table, and a positive integer k, you need to return the k-th smallest number in this table.

Example 1:

1
2
3
4
5
6
7
8
9
Input: m = 3, n = 3, k = 5
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6
3	6	9

The 5-th smallest number is 3 (1, 2, 2, 3, 3).

Example 2:

1
2
3
4
5
6
7
8
Input: m = 2, n = 3, k = 6
Output: 
Explanation: 
The Multiplication Table:
1	2	3
2	4	6

The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6).

Note:

  1. The m and n will be in the range [1, 30000].
  2. The k will be in the range [1, m * n]
Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from heapq import *
class Solution:
    def findKthNumber(self, m, n, k):
        """
        :type m: int
        :type n: int
        :type k: int
        :rtype: int
        """
        def countLower(m, n, num):
            count = 0
            for row in range(1, min(m, num) + 1):
                temp = num // row
                if temp > n: 
                    count += n
                else:
                    count += temp
            return count
        
        if m > n: n, m = m, n
        high = m * n
        low = 1
        while low < high:
            mid = (low + high) // 2
            if countLower(m, n, mid) < k:
                low = mid + 1
            else:
                high = mid 
        return low
0%