# 668. Kth Smallest Number in Multiplication Table
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:
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).
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).
# Solution
Approach 1: brute force. Calculate all multiplication results, sort them, and pick out the kth. Time: O(mn*log(mn))
.
Approach 2: heap. Observation: for each row, value[i+1] = value[i] + value[0]. So in a heap we store (value, row_number), and 'explore' a node by adding it's next smallest: (value + row_number, row_number). Time: O(m<heapify> + k*logm)
-- good for small ks.
Approach 3: binary search. Observation: for each row, value[i] = (i+1) * value[0]. We can calculate total_nums<=x by adding up nums<=x for each row, then binary search for the first number that has at least k numbers less or equal to it. Time: O(log(mn) * m)
-- the time doesn't have to do with k!
# Code (Python)
Approach 2:
import heapq
class Solution:
def findKthNumber(self, m, n, k):
"""
:type m: int
:type n: int
:type k: int
:rtype: int
"""
heap = [(row_num, row_num) for row_num in range(1, m+1)]
heapq.heapify(heap)
for i in range(k):
value, row_num = heapq.heappop(heap)
if i == k - 1:
return value
if value + row_num <= row_num * n:
heapq.heappush(heap, (value + row_num, row_num))
Approach 3:
def findKthNumber(self, m, n, k):
left, right = 1, m * n
while left < right:
mid = (left + right) // 2
nums_less_or_equal = self._nums_less_or_equal_to(mid, m, n)
if nums_less_or_equal >= k:
right = mid # if nums_less_or_equal == k, we can return mid immediately
else:
left = mid + 1
return left
# need to count in the nums equal to the target too, otherwise we get the (k+1)th smallest
def _nums_less_or_equal_to(self, target, m, n):
total = 0
for row_num in range(1, m + 1):
total += min(n, target // row_num)
return total
# Code (C++)
Approach 1:
Approach 2:
Approach 3: