668. Kth Smallest Number in Multiplication Table

leetcode hard

#csharp#hard#leetcode#math#matrix#search#two-pointers

Task

Почти каждый использовал таблицу умножения. Таблица умножения размером 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.

C# solution

matched/original

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 - left) / 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;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int FindKthNumber(int m, int n, int k) {
        int left = 1, right = m * n;
        
        while (left < right) {
            int mid = left + (right - left) / 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 += min(x / i, n);
        }
        return count;
    }
}

Java solution

matched/original

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;
    }
}

JavaScript solution

matched/original

var findKthNumber = function(m, n, k) {
    let left = 1, right = m * n;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countLessEqual(m, n, mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};

function countLessEqual(m, n, x) {
    let count = 0;
    for (let i = 1; i <= m; i++) {
        count += Math.min(Math.floor(x / i), n);
    }
    return count;
}

Python solution

matched/original

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

Explanation

Algorithm

Установка границ поиска:

Установите нижнюю границу left равной 1 и верхнюю границу right равной m * n.

Бинарный поиск:

Используйте бинарный поиск, чтобы найти k-й наименьший элемент.

Для каждого среднего значения mid, посчитайте количество элементов в таблице умножения, которые меньше или равны mid.

Проверка количества элементов:

Если количество элементов меньше k, увеличьте нижнюю границу (left).

Если количество элементов больше или равно k, уменьшите верхнюю границу (right).

😎