Skip to content

Commit 4882b9d

Browse files
qiyuangongqiyuangong
committed
Refine 668_Kth_Smallest_Number_in_Multiplication_Table
1 parent 7e0d4d5 commit 4882b9d

4 files changed

+61
-18
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -175,6 +175,7 @@ I'm currently working on [Analytics-Zoo](https://github.com/intel-analytics/anal
175175
| 628 | [Maximum Product of Three Numbers](https://leetcode.com/problems/maximum-product-of-three-numbers/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/628_Maximum_Product_of_Three_Numbers.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/628_Maximum_Product_of_Three_Numbers.java) | Actually, we should only care about min1, min2 and max1-max3, to find these five elements, we can use 1. Brute force, O(n^3) and O(1)<br>2. Sort, O(nlogn) and O(1)<br>3. Single scan with 5 elements keep, O(n) and O(1) |
176176
| 654 | [Maximum Binary Tree](https://leetcode.com/problems/maximum-binary-tree/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/654_Maximum_Binary_Tree.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/654_Maximum_Binary_Tree.java) | 1. Divide and conquer, recursive, O(n^2)<br>2. Monotonic stack, O(n) |
177177
| 665 | [Non-decreasing Array](https://leetcode.com/problems/non-decreasing-array/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/665_Non-decreasing_Array.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/665_Non-decreasing_Array.java) | 1. Find the broken index, then check this point, O(n) and O(1)<br>2. Replace broken point with correct value, then check if there are more than 1 broken point, O(n) and O(1) |
178+
| 668 | [Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/668_Kth_Smallest_Number_in_Multiplication_Table.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/668_Kth_Smallest_Number_in_Multiplication_Table.java) [Cpp](https://github.com/qiyuangong/leetcode/blob/master/cpp/668_Kth_Smallest_Number_in_Multiplication_Table.cpp) | Binary search, O(mlog(mn) and O(1) |
178179
| 671 | [Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/671_Second_Minimum_Node_In_a_Binary_Tree.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/671_Second_Minimum_Node_In_a_Binary_Tree.java) | Note that min value is root: 1. Get all values then find result, O(n) and O(n)<br>2. BFS or DFS traverse the tree, then find the reslut, O(n) and O(n)|
179180
| 674 | [Longest Continuous Increasing Subsequence](https://leetcode.com/problems/longest-continuous-increasing-subsequence/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/674_Longest_Continuous_Increasing_Subsequence.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/674_Longest_Continuous_Increasing_Subsequence.java) | Scan nums once, check nums[i] < nums[i+1], if not reset count, O(n) and O(1) |
180181
| 680 | [Valid Palindrome II](https://leetcode.com/problems/valid-palindrome-ii/) | [Python](https://github.com/qiyuangong/leetcode/blob/master/python/680_Valid_Palindrome_II.py) [Java](https://github.com/qiyuangong/leetcode/blob/master/java/680_Valid_Palindrome_II.java) | Recursively check s[left == end, when not equal delete left or right. |

‎cpp/668_Kth_Smallest_Number_in_Multiplication_Table.cpp

Lines changed: 19 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -1,26 +1,27 @@
11
class Solution {
22
public:
3-
#define ll long long int
4-
5-
bool valid(ll x, int m, int n, int k){
6-
int cnt=0;
7-
for(int i=1;i<=m;i++){
8-
cnt+=n<x/i?n:x/i;
9-
if(x/i==0)break;
3+
#define ll long long int
4+
bool valid(ll x, int m, int n, int k) {
5+
int cnt = 0;
6+
for (int i = 1; i <= m; i++) {
7+
cnt += n < x / i ? n : x / i;
8+
if (x / i == 0)
9+
break;
1010
}
11-
return cnt>=k;
11+
return cnt >= k;
1212
}
13-
13+
1414
int findKthNumber(int n1, int n2, int k) {
15-
ll l=0, r=n1*n2,ans;
16-
while(l<=r){
17-
ll m = l +(r-l)/2;
18-
if(valid(m,n1,n2,k)){
19-
ans=m;
20-
r=m-1;
21-
}
22-
else{
23-
l=m+1;
15+
ll l = 0, r = n1 * n2, ans;
16+
while (l <= r) {
17+
// ith row [i, 2*i, 3*i, ..., n*i]
18+
// for each column, k = x // i
19+
ll m = l + (r - l) / 2;
20+
if (valid(m, n1, n2, k)) {
21+
ans = m;
22+
r = m - 1;
23+
} else {
24+
l = m + 1;
2425
}
2526
}
2627
return ans;

‎java/668_Kth_Smallest_Number_in_Multiplication_Table.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
class Solution {
2+
// https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/solution/
3+
public boolean enough(int x, int m, int n, int k) {
4+
int count = 0;
5+
for (int i = 1; i <= m; i++) {
6+
count += Math.min(x / i, n);
7+
}
8+
return count >= k;
9+
}
10+
11+
public int findKthNumber(int m, int n, int k) {
12+
int lo = 1, hi = m * n;
13+
while (lo < hi) {
14+
// ith row [i, 2*i, 3*i, ..., n*i]
15+
// for each column, k = x // i
16+
int mi = lo + (hi - lo) / 2;
17+
if (!enough(mi, m, n, k)) lo = mi + 1;
18+
else hi = mi;
19+
}
20+
return lo;
21+
}
22+
}

‎python/668_Kth_Smallest_Number_in_Multiplication_Table.py

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
class Solution:
2+
def findKthNumber(self, m: int, n: int, k: int) -> int:
3+
# https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/solution/
4+
def enough(x):
5+
count = 0
6+
# ith row [i, 2*i, 3*i, ..., n*i]
7+
# for each column, k = x // i
8+
for i in range(1, m+1):
9+
count += min(x // i, n)
10+
return count >= k
11+
12+
lo, hi = 1, m * n
13+
while lo < hi:
14+
mi = (lo + hi) // 2
15+
if not enough(mi):
16+
lo = mi + 1
17+
else:
18+
hi = mi
19+
return lo

0 commit comments

Comments
 (0)