решение матричной задачи - найдите первый столбец со значением 1 в матрице 1 и 0

Question

Был задан этот вопрос в цикле кодирования:

Учитывая матрицу из 0 и 1, где, в любой строке - значения будут в порядке возрастания. т.е. 1 всегда после 0. Рассмотрим пример:

0,0,0,1,1
0,0,1,1,1
0,0,0,0,1
1,1,1,1,1
0,0,0,0,0

Найдите первый столбец с 1. ( слева - справа )

В этом случае первый столбец ( в строке 4 ) есть 1. Ответ: 1

Я предложил мудрый обход столбцов по всем строкам и завершился, когда текущий столбец встречает 1 в любой из строк.

Поскольку производительность в худшем случае равна n * n (при сравнении каждого элемента в матрице), интервьюер был недоволен и искал эффективное решение - что такое эффективное решение здесь?

Answer 1

Воспользуйтесь тем, что строки отсортированы, что видно из "в любой строке - значения будут в порядке возрастания. То есть 1 всегда после 0"

Пусть там будет m строк и n столбцов. Выполните двоичный поиск в первой строке, чтобы выяснить первый 1 и сохраните этот индекс в некоторой переменной, скажем index (Можно подумать о лучшем имени переменной. Я просто сосредоточен здесь на оптимальном решении проблемы.) Продолжить бинарный поиск по каждой строке, обновите index, если первый столбец, содержащий 1, имеет меньший индекс, чем index. После выполнения бинарного поиска по каждой строке вы получите результат в переменной index.

Сложность времени: m строки * log2 (n столбцы), т. Е. O(m * log2(n)).

Это подход, который я мог бы придумать, который лучше, чем метод грубой силы, имеющий O(mn) сложность времени. Я не думаю, что был бы более оптимальный подход с точки зрения сложности времени и пространства, поскольку нужно искать первые 1 в каждой строке.

[Не думаю, что мне следует добавлять подробности о том, как выполнить бинарный поиск, чтобы выяснить первый столбец, содержащий 1. Если кто-то плохо знаком с бинарным поиском, я оставляю эту тривиальную часть в качестве упражнения.]