# 668    Kth Smallest Number in Multiplication Table

## 668. [Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/description/)

## 1. Question

Nearly every one have used the [Multiplication Table](https://en.wikipedia.org/wiki/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:**

```
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:**

```
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]

## 2. Implementation

**(1) Binary Search**

思路: [Kth Smallest Element in a Sorted Matrix](https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/) 一样的解法

```java
class Solution {
    public int findKthNumber(int m, int n, int k) {
        int start = 1, end = m * n, mid = 0;

        while (start < end) {
            mid = start + (end - start) / 2;

            int count = searchAndCount(mid, m, n);

            if (count < k) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return start;
    }

    public int searchAndCount(int target, int m, int n) {
        int row = m, col = 1, count = 0;

        while (row >= 1 && col <= n) {
            if (row * col <= target) {
                count += row;
                ++col;
            }
            else {
                --row;
            }
        }
        return count;
    }
}
```

**(2) Heap**

```java
class Solution {
    public int findKthNumber(int m, int n, int k) {
        PriorityQueue<CellInfo> minHeap = new PriorityQueue<>();

        for (int i = 1; i <= n; i++) {
            minHeap.add(new CellInfo(1, i, i));
        }

        for (int i = 2; i <= k; i++) {
            CellInfo curCell = minHeap.remove();
            // System.out.println("current value: " + curCell.val);
            int curRow = curCell.row;
            int curCol = curCell.col;

            if (curRow + 1 <= m) {
                minHeap.add(new CellInfo(curRow + 1, curCol, (curRow + 1) * curCol));
            }
        }
        return minHeap.peek().val;
    }

    class CellInfo implements Comparable<CellInfo> {
        int row, col, val;

        public CellInfo(int row, int col, int val) {
            this.row = row;
            this.col = col;
            this.val = val;
        }

        public int compareTo(CellInfo that) {
            return this.val - that.val;
        }
    }
}
```

## 3. Time & Space Complexity

**Binary Search:** 时间复杂度O((m+n)log(mn)), 空间复杂度O(1）

**Heap:** 时间复杂度O(m \* n \* logn), 空间复杂度O(logn), heap存储最多n个(列数)个数
