Сложность: 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).
😎 Решение:
class Solution:
def findKthNumber(self, m: int, n: int, k: int) -> int:
def count_less_equal(x):
count = 0
for i in range(1, m + 1):
count += min(x // i, n)
return count
left, right = 1, m * n
while left < right:
mid = (left + right) // 2
if count_less_equal(mid) < k:
left = mid + 1
else:
right = mid
return left
Ставь 👍 и забирай 📚 Базу знаний