Найдите пропущенное число в диапазоне [1, N*M+1], представленном в виде матрицы размера N*M
Дана матрица размера N x M mat[][] , где все элементы являются натуральными числами, начиная с 1 и непрерывны, кроме 1 элемента, найдите этот элемент.
Примеры :
Input: mat[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 11, 12, 13}}
N = 3, M = 4
Output: 10
Explanation: Missing number is 10 at row no 3.Input: mat[][] = {{1, 2, 3},
{5, 6, 7},
{8, 9, 10}}
N = 3, M = 3
Output: 4
Подход : проблема может быть решена путем проверки кратных M в последнем элементе каждой строки матрицы, если они не совпадают, то недостающий элемент находится в этой строке. Примените линейный поиск и найдите его.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O(N + M)
Вспомогательное пространство : O(1)
Эффективный подход . Эффективный подход заключается в проверке кратности последнего элемента в строках с использованием алгоритма бинарного поиска. Если он не совпадает, то отсутствующий элемент находится в этой строке или ее предыдущих строках, а если он соответствует, то отсутствующий элемент находится в следующих строках. Сначала найдите эту строку с помощью двоичного поиска, а затем примените двоичный поиск в этой строке таким же образом, чтобы найти столбец.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность : O (log N + log M)
Вспомогательное пространство : O(1)