Massive Algorithms: LeetCode 668 - Kth Smallest Number in Multiplication Table

LeetCode 668 - Kth Smallest Number in Multiplication Table

https://leetcode.com/problems/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 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:

The m and n will be in the range [1, 30000].
The k will be in the range [1, m * n]

X.
https://leetcode.com/articles/kth-smallest-number-in-multiplication-table/

\text{k}

and

\text{m*n}

are up to

9 * 10^8

, linear solutions will not work. This motivates solutions with

\log

complexity, such as binary search.

Algorithm

Let's do the binary search for the answer

\text{A}

Say enough(x) is true if and only if there are

\text{k}

or more values in the multiplication table that are less than or equal to

\text{x}

. Colloquially, enough describes whether

\text{x}

is large enough to be the

k^{th}

value in the multiplication table.

Then (for our answer

\text{A}

), whenever

\text{x ≥ A}

, enough(x) is True; and whenever

\text{x &lt; A}

, enough(x) is False.

In our binary search, our loop invariant is enough(hi) = True. At the beginning, enough(m*n) = True, and whenever hi is set, it is set to a value that is "enough" (enough(mi) = True). That means hi will be the lowest such value at the end of our binary search.

This leaves us with the task of counting how many values are less than or equal to

\text{x}

. For each of

\text{m}

rows, the

i^{th}

row looks like

\text{[i, 2*i, 3*i, ..., n*i]}

. The largest possible

\text{k*i ≤ x}

that could appear is

\text{k = x // i}

. However, if

\text{x}

is really big, then perhaps

\text{k &gt; n}

, so in total there are

\text{min(k, n) = min(x // i, n)}

values in that row that are less than or equal to

\text{x}

After we have the count of how many values in the table are less than or equal to

\text{x}

, by the definition of enough(x), we want to know if that count is greater than or equal to

\text{k}

Time Complexity: $O(m * \log (m*n))$ . Our binary search divides the interval $\text{[lo, hi]}$ into half at each step. At each step, we call enough which requires $O(m)$ time.
Space Complexity: $O(1)$ . We only keep integers in memory during our intermediate calculations.

public boolean enough(int x, int m, int n, int k) {

int count = 0;

for (int i = 1; i <= m; i++) {

count += Math.min(x / i, n);

}

return count >= k;

}

public int findKthNumber(int m, int n, int k) {

int lo = 1, hi = m * n;

while (lo < hi) {

int mi = lo + (hi - lo) / 2;

if (!enough(mi, m, n, k))

lo = mi + 1;

else

hi = mi;

}

return lo;

}

https://blog.csdn.net/he1533/article/details/77774526
首先看一下什么是Multiplication Table：https://en.wikipedia.org/wiki/Multiplication_table
我们可以清楚的看到第i行第j列的数等于i*j，根据这一点，可以很快的判断一个数x在n×m表中是第几大的：
第i行小于等于x的数有min（n，x/i）个，将m行的值加起来即可。
根据这一特点我们有了一个判断一个数x是在第k大的数之前还是之后的工具，有了这一工具，我们就可以使用二分法来获取第k大的数。
但获取到的数不一定在这个表里面，这时，找到表中比这个数小的最大的数即可。
复杂度为O(nlgk) n<=m;(第k大的数一定不大于k)。

http://www.cnblogs.com/grandyang/p/8367505.html
这道题跟之前那道Kth Smallest Element in a Sorted Matrix没有什么太大的区别，这里的乘法表也是各行各列分别有序的。那么之前帖子里的方法都可以拿来参考。之前帖子中的解法一在这道题中无法通过OJ，维护一个大小为k的优先队列实在是没有利用到这道题乘法表的特点，但是后两种解法都是可以的。为了快速定位出第K小的数字，我们采用二分搜索法，由于是有序矩阵，那么左上角的数字一定是最小的，而右下角的数字一定是最大的，所以这个是我们搜索的范围，然后我们算出中间数字mid，由于矩阵中不同行之间的元素并不是严格有序的，所以我们要在每一行都查找一下mid，由于乘法表每行都是连续数字1，2，3...乘以当前行号（从1开始计数），所以我们甚至不需要在每行中使用二分查找，而是直接定位出位置。具体做法是，先比较mid和该行最后一个数字的大小，最后一数字是n * i，i是行数，n是该行数字的个数，如果mid大的话，直接将该行所有数字的个数加入cnt，否则的话加上mid / i，比如当前行是2, 4, 6, 8, 10，如果我们要查找小于7的个数，那么就是7除以2，得3，就是有三个数小于7，直接加入cnt即可。这样我们就可以快速算出矩阵中所有小于mid的个数，根据cnt和k的大小关系，来更新我们的范围，循环推出后，left就是第K小的数字

     int findKthNumber(int m, int n, int k) {
         int left = 1, right = m * n;
         while (left < right) {
             int mid = left + (right - left) / 2, cnt = 0;
             for (int i = 1; i <= m; ++i) {
                 cnt += (mid > n * i) ? n : (mid / i);
             }
             if (cnt < k) left = mid + 1;
             else right = mid;
         }
         return right;
     }

下面这种解法在统计小于mid的数字个数的方法上有些不同，并不是逐行来统计，而是从左下角的数字开始统计，如果该数字小于mid，说明该数字及上方所有数字都小于mid，cnt加上i个，然后向右移动一位继续比较。如果当前数字小于mid了，那么向上移动一位，直到横纵方向有一个越界停止，其他部分都和上面的解法相同

     int findKthNumber(int m, int n, int k) {
         int left = 1, right = m * n;
         while (left < right) {
             int mid = left + (right - left) / 2, cnt = 0, i = m, j = 1;
             while (i >= 1 && j <= n) {
                 if (i * j <= mid) {
                     cnt += i;
                     ++j;
                 } else {
                     --i;
                 }
             }
             if (cnt < k) left = mid + 1;
             else right = mid;
         }
         return right;
     }

下面这种解法由网友bambu提供，是对解法二的优化，再快一点，使用除法来快速定位新的j值，然后迅速算出当前行的小于mid的数的个数，然后快速更新i的值，这比之前那种一次只加1或减1的方法要高效许多，感觉像是解法一和解法二的混合体

     int findKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        while (left < right) {
            int mid = left + (right - left) / 2, cnt = 0, i = m, j = 1;
            while (i >= 1 && j <= n) {
                 int t = j;
                 j = (mid > n * i) ? n + 1 : (mid / i + 1);
                 cnt += (j - t) * i;
                 i = mid / j;
             }
            if (cnt < k) left = mid + 1;
            else right = mid;
        }
        return right;
     }

https://discuss.leetcode.com/topic/101132/java-solution-binary-search
It counts all values smaller or equal than v in each column I guess. Using min is to avoid the count is larger than row number. It's a nice solution.

    public int findKthNumber(int m, int n, int k) {
     int low = 1 , high = m * n + 1;
        
     while (low < high) {
         int mid = low + (high - low) / 2;
         int c = count(mid, m, n);
         if (c >= k) high = mid;
            else low = mid + 1;
     }
        
     return high;
    }
    
    private int count(int v, int m, int n) {
       int count = 0;
       for (int i = 1; i <= m; i++) {
         int temp = Math.min(v / i , n);
         count += temp;
       }
       return count;
     }

https://stackoverflow.com/questions/33464901/using-binary-search-to-find-k-th-largest-number-in-nm-multiplication-table
https://leetcode.com/articles/kth-smallest-number-in-multiplication-table/
Create the multiplication table and sort it, then take the

Time Complexity: $O(m*n)$ to create the table, and $O(m*n\log(m*n))$ to sort it.
Space Complexity: $O(m*n)$ to store the table.

Time Complexity: $O(k * m \log m) = O(m^2 n \log m)$ . Our initial heapify operation is $O(m)$ . Afterwards, each pop and push is $O(m \log m)$ , and our outer loop is $O(k) = O(m*n)$
Space Complexity: $O(m)$ . Our heap is implemented as an array with $m$ elements.

Maintain a heap of the smallest unused element of each row. Then, finding the next element is a pop operation on the heap.

Algorithm

Our heap is going to consist of elements

\text{(val, root)}

, where

\text{val}

is the next unused value of that row, and

\text{root}

was the starting value of that row.

We will repeatedly find the next lowest element in the table. To do this, we pop from the heap. Then, if there's a next lowest element in that row, we'll put that element back on the heap.

    public int findKthNumber(int m, int n, int k) {
        PriorityQueue<Node> heap = new PriorityQueue<Node>(m,
            Comparator.<Node> comparingInt(node -> node.val));

        for (int i = 1; i <= m; i++) {
            heap.offer(new Node(i, i));
        }

        Node node = null;
        for (int i = 0; i < k; i++) {
            node = heap.poll();
            int nxt = node.val + node.root;
            if (nxt <= node.root * n) {
                heap.offer(new Node(nxt, node.root));
            }
        }
        return node.val;
    }

class Node {
    int val;
    int root;
    public Node(int v, int r) {
        val = v;
        root = r;
    }
}

Approach #1: Brute Force

Create the multiplication table and sort it, then take the

k^{th}

element.

Time Complexity: $O(m*n)$ to create the table, and $O(m*n\log(m*n))$ to sort it.
Space Complexity: $O(m*n)$ to store the table.

public int findKthNumber(int m, int n, int k) {

int[] table = new int[m * n];

for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

table[(i - 1) * n + j - 1] = i * j;

}

Arrays.sort(table);

return table[k - 1];

}

LeetCode 668 - Kth Smallest Number in Multiplication Table

Labels

Popular Posts