Сложность: hard
Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).
Даны три целых числа m, n и k. Верните k-й наименьший элемент в таблице умножения размером m x n.
Пример:
Input: m = 3, n = 3, k = 5
Output: 3
Explanation: The 5th smallest number is 3.
👨💻 Алгоритм:
1⃣Установка границ поиска:
Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.
2⃣Бинарный поиск:
Используйте бинарный поиск, чтобы найти k-й наименьший элемент.
Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.
3⃣Проверка количества элементов:
Если количество элементов меньше k, увеличьте нижнюю границу (left).
Если количество элементов больше или равно k, уменьшите верхнюю границу (right).
😎 Решение:
public class Solution {
public int findKthNumber(int m, int n, int k) {
int left = 1, right = m * n;
while (left < right) {
int mid = (left + right) / 2;
if (countLessEqual(m, n, mid) < k) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
private int countLessEqual(int m, int n, int x) {
int count = 0;
for (int i = 1; i <= m; i++) {
count += Math.min(x / i, n);
}
return count;
}
}Ставь 👍 и забирай 📚 Базу знаний