668. Kth Smallest Number in Multiplication Table

LeetCode hard original: C# #csharp #hard #leetcode #math #matrix #search #two-pointers

Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.

LeetCode Static

Почти каждый использовал таблицу умножения. Таблица умножения размером m x n - это целочисленная матрица mat, где mat[i][j] == i * j (индексация начинается с 1).

given три целых числа m, n и k. return k-й наименьший element в таблице умножения размером m x n.

Esempio

Input: m = 3, n = 3, k = 5

Output: 3

Explanation: The 5th smallest number is 3.

C# soluzione

abbinato/originale

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++ soluzione

bozza automatica, rivedere prima dell'invio

#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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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 soluzione

abbinato/originale

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

Algorithm

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

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

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

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

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

Проверка количества elementов:

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

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

😎

Vacancies for this task

offerte attive with overlapping task tags are mostrati.

Tutte le offerte

Non ci sono ancora offerte attive.