|
2 | 2 |
|
3 | 3 | import java.util.PriorityQueue;
|
4 | 4 |
|
5 |
| -/** |
6 |
| - * 668. Kth Smallest Number in Multiplication Table |
7 |
| - * |
8 |
| - * Nearly every one have used the Multiplication Table. |
9 |
| - * But could you find out the k-th smallest number quickly from the multiplication table? |
10 |
| - * Given the height m and the length n of a m * n Multiplication Table, |
11 |
| - * and a positive integer k, you need to return the k-th smallest number in this table. |
12 |
| -
|
13 |
| - Example 1: |
14 |
| - Input: m = 3, n = 3, k = 5 |
15 |
| - Output: |
16 |
| - Explanation: |
17 |
| - The Multiplication Table: |
18 |
| - 1 2 3 |
19 |
| - 2 4 6 |
20 |
| - 3 6 9 |
21 |
| -
|
22 |
| - The 5-th smallest number is 3 (1, 2, 2, 3, 3). |
23 |
| -
|
24 |
| -
|
25 |
| - Example 2: |
26 |
| - Input: m = 2, n = 3, k = 6 |
27 |
| - Output: |
28 |
| - Explanation: |
29 |
| - The Multiplication Table: |
30 |
| - 1 2 3 |
31 |
| - 2 4 6 |
32 |
| -
|
33 |
| - The 6-th smallest number is 6 (1, 2, 2, 3, 4, 6). |
34 |
| -
|
35 |
| - Note: |
36 |
| -
|
37 |
| - The m and n will be in the range [1, 30000]. |
38 |
| - The k will be in the range [1, m * n] |
39 |
| - */ |
40 |
| - |
41 | 5 | public class _668 {
|
42 | 6 | public static class Solution1 {
|
43 | 7 | /**
|
@@ -65,7 +29,9 @@ public int findKthNumber(int m, int n, int k) {
|
65 | 29 | }
|
66 | 30 |
|
67 | 31 | public static class Solution2 {
|
68 |
| - /**reference: https://discuss.leetcode.com/topic/101132/java-solution-binary-search*/ |
| 32 | + /** |
| 33 | + * reference: https://discuss.leetcode.com/topic/101132/java-solution-binary-search |
| 34 | + */ |
69 | 35 | public int findKthNumber(int m, int n, int k) {
|
70 | 36 | int low = 1;
|
71 | 37 | int high = m * n + 1;
|
|
0 commit comments