Найдите строку, представляющую наименьшее целое число в отсортированной по строке матрице

Question

Мне задали этот вопрос в недавнем интервью по телефону на Java:

Вам предоставляется двоичная (0-1) матрица NxN со следующими свойствами:

• Каждая строка сортируется (последовательность из 0 следует за последовательностью из 1)
• Каждая строка представляет целое число без знака (путем чтения битов)
• Каждый ряд уникален

Пример:

0 1 1
1 1 1
0 0 1

Значения битов в каждой строке сортируются, и строки представляют целые числа 3, 7 и 1.

Найдите строку, представляющую наименьшее целое число. В приведенном выше примере ответом является строка 3, представляющая целое число 1.

Я начал с грубой силы квадратичной сложности. Интервьюер ответил, что я не эксплуатирую отсортированное имущество.

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

Буду признателен, если кто-нибудь подскажет, как его улучшить.

Другой пример:

0 1 1 1
0 0 0 1
0 0 0 0
1 1 1 1

Ответом будет строка 3, представляющая целое число 0.

Answer 1

Оптимизированная версия @ codaddict

int best = N;
int answer = -1;

for(int i=0;i<N;i++)
   for(int j=0;j<best;j++) 
       if (arr[i][j] != 0) {
          best = j;
          answer = i;
        }

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

Answer 2

Вы должны начать с последнего столбца и проверить, равна ли сумма элемента N-1, как только вы нашли столбец с суммой = N-1, найдите столбец, содержащий 0, и это тот, который вы ищем ...

Answer 3

Я написал алгоритм O (n), аналогичный тому, что был указан выше, мы начинаем с левого верхнего угла и работаем вниз:

a = [
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [0, 0, 0, 0],
        [1, 1, 1, 1]
    ]
a2 = [
        [0, 0, 0, 0],
        [0, 1, 1, 1],
        [0, 0, 0, 1],
        [1, 1, 1, 1]
    ]

def search(a):
    n = len(a)
    c = 0
    r = 0
    best_row = 0
    while c<n and r<n:
        if a[r][c] == 0:
            c += 1
        else:
            best_row = r
            r += 1

    if c==n : best_row = r
    print( " best row: %d" % best_row )

search( a )
search( a2 )

Answer 4

Я не знаю, допустимо ли это, но если оно отсортировано, вам не нужно просто преобразовывать каждую строку в десятичное число и выбирать строку с более низким. Пример:

[0111] -> 7
[0011] -> 3
[0000] -> 0
[0001] -> 1

Решением является строка со значением 0. ИЛИ?