Найдите пропущенное число в диапазоне [1, N*M+1], представленном в виде матрицы размера N*M

Опубликовано: 20 Сентября, 2022

Дана матрица размера 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)

РЕКОМЕНДУЕМЫЕ СТАТЬИ