668 Kth Smallest Number in Multiplication Table

668. Kth Smallest Number in Multiplication Table

1. Question

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

Given the heightmand the lengthnof am * nMultiplication Table, and a positive integerk, you need to return thek-thsmallest 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. Themandnwill be in the range [1, 30000].

2. Thekwill be in the range [1, m * n]

2. Implementation

(1) Binary Search

思路: Kth Smallest Element in a Sorted Matrix 一样的解法

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

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个(列数)个数