# 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.
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).
Approach 1: brute force. Calculate all multiplication results, sort them, and pick out the kth. Time:
Approach 2: heap. Observation: for each row, value[i+1] = value[i] + value. 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. 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)
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))
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++)