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

Ответ 1

Начните с строки 1. Идите прямо до первого 1. Затем перейдите к строке 2, но оставайтесь в том же столбце и повторите процесс перехода до тех пор, пока не нажмете 1. Делайте это повторно. Строка, в которой вы последний шаг вышла правильно, - это ваш ответ.

Это решение O (N + M) (для матрицы NxM или O (N) для квадратной матрицы NxN, как указано в вопросе).

Используя ваш пример:

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

Здесь . представляет пройденный путь:

. . 1 1
0 . . .
0 0 0 . . Last right step, therefore this is our answer
1 1 1 1 .

Это решение работает с неквадратичными матрицами, сохраняя худшую эффективность O (N + M) для матрицы NxM.

Почему это работает? Гарантия того, что числа будут отсортированы, означает, что каждая строка будет серией из 0, за которой следует серия из 1. Таким образом, величина строки эквивалентна тому, насколько далеко вы можете идти до удара 1. Итак, если строка может когда-либо занять вас, просто следуя за 0, тогда она должна быть длиннее, чем мы уже обрабатывали.

Код Python:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

ans, j = 0, 0
for i, row in enumerate(li):
  while j < len(row) and row[j] == 0:
    j += 1
    ans = i

print "Row", ans+1, "".join(map(str, li[ans]))

Существует также более простое решение из-за ограничений всегда иметь квадратную матрицу NxN и различные строки вместе. Вместе они означают, что строка с наименьшим значением будет либо 0 0 ... 0 1, либо 0 0 ... 0 0. Это связано с тем, что в матрице представлено N из N + 1 возможных чисел, поэтому "недостающее" число равно 0 (в этом случае наименьшее представленное значение равно 1) или что-то другое (наименьшее значение равно 0).

С помощью этого знания мы проверим второй столбец справа на 0. Когда мы его найдем, мы посмотрим на его право, и если он содержит другое 0, мы получим наш ответ (может быть только одна строка, заканчивающаяся на 0). В противном случае мы продолжаем искать столбец для другого 0. Если мы не найдем другого 0, то первое, что мы нашли, это строка, которую мы ищем (может быть только одна строка, заканчивающаяся на 01, и поскольку ни один не заканчивается на 00, это самый маленький).

Код Python:

li = [[0, 1, 1, 1],
      [0, 0, 0, 1],
      [0, 0, 0, 0],
      [1, 1, 1, 1]]

for i, row in enumerate(li):
  if row[-2] == 0:
    ans = i
    if row[-1] == 0:
      break

print "Row", ans+1, "".join(map(str, li[ans]))

Это решение отвечает на вопрос с наименьшими трудностями в O (N), но обобщение его на обработку неквадратных матриц NxM или нечетких чисел сделает его наихудшую эффективность O (N ^ 2). Я лично предпочитаю первое решение.

Ответ 2

самое низкое число должно быть 0 или 1. (поскольку дублирование не производится, и строки сортируются). все, что вам нужно сделать, это перейти к последнему столбцу, если ti содержит 0, самое низкое число равно 0, самое меньшее - 1.

EDIT - объяснение
В N строках с указанным ограничением может быть максимум N+1 уникальных значений.
так что наверняка по крайней мере 0 или 1 должны быть в матрице....

Изменить 2 - алгоритм

//assuming the matrix is 0 indexed base
for i = 0...N-1
  if M[i][N-1] == 0
    return "Value is 0 in row i";
for i = 0...N-1
  if M[i][N-2] == 0
    return "Value is 1 in row i";
//because of the explanation above the flow will never reach here.

Ответ 3

Так как числа уникальны, и поскольку цифры сортируются, то совершенно ясно, что для любого значения N наименьшее число может быть либо из вида [0 (N-1 раз), за которым следует 1], либо 0 ( N раз).

Например, для N = 4 наименьшее число может быть 0001 или 0000.

Другими словами, вторая последняя цифра номера, которую мы хотим найти HAS, равна 0. И последняя цифра может быть либо 0, либо 1

Затем эта проблема сводится к простому нахождению этих шаблонов в массиве, что можно сделать с помощью простого цикла

int rowNum = -1;

for(int i=0;i<N;i++)
{
    if(arr[i][N-2]==0) //Second last digit is 0. Hence the number could be min.
    {
        rowNum = i;

        if(arr[i][N-1]==1) // If number of the form 0001 was found, keep looking for 0000
        {
            continue;
        }
        else
         //If number of the form 0000 was found, exit. 
         //No other number can be lesser than 0000
        {
            break;
        }
    }
}
return rowNum;

Этот алгоритм имел бы сложность O (n)

Ответ 4

Вы хотите найти строки с максимальным количеством нулей.

• Начните с arr[0][0]
• Если это 0, проверьте элемент в направлении справа от него, arr[0][1].
• Если это не 0, пропустите эту строку и начните проверку элемента в следующая строка ниже текущего элемента.

Продолжайте делать, пока вы не пройдете последний столбец последней строки/последнего, или вы найдете строку со всеми нулями.

Алгоритм:

i = 0 
j = 0 
answer = 0 

# continue till i is a valid index.
while(i<N) 

        # continue till j is valid index and ele is 0.
        while(j < N AND arr[i][j] == 0)

                # move towards right.
                j++ 

                #update answer.
                answer = i 

                # found a row with all zeros.
                if(j == N)  
                        break all loops.
                end-if

        end-while

        # skip current row..continue on next row.    
        i++ 

end-while

print answer

Сложность этого O(N+N), которая O(N), которая является линейной.

реализация Java

Связанный с этим вопрос, который использует точный трюк

Как эффективно искать в упорядоченной матрице?

Ответ 5

Так как бит в каждой строке сортируется, как только вы нашли 1 бит, все биты справа тоже должны быть 1. Другими словами, массив хранит только значения формы 2 ^ n-1.

Таким образом, ответ - это строка с наименьшими наименьшими значениями.

Однако, так как только 2 ** m-1 записи могут присутствовать, и их n, и нет двух одинаковых, мы можем вывести больше - для любого N есть N + 1 таких значений. Поэтому либо 0, либо 1 должны присутствовать, поскольку мы знаем, что дубликатов нет.

Итак, найдите пустую строку (которая представляет собой только один номер с самым правым столбцом нуль). Если вы его не нашли, ответ будет равен 1, иначе он будет 0.

O (N)

Ответ 6

Start at the top-left.

The first row is the best row so far.

Repeat until you reach the bottom:
  If you're not already over a 1:
    Go right until you find a 1.
    This row is the best row so far.
  Go down one row.

Report the best row that was found.

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

Ответ 7

Как прокрутить каждую строку в обратном порядке и проверить, где заканчиваются 1-й конец и нули?

На самом деле гарантировано, что в NxN худший случай состоит в том, что 0 не будет. Таким образом, вы можете просто проверить последние 2 записи каждой строки. Это делает его линейным.

Поскольку мое объяснение не было понято, здесь он находится в несколько псевдокоде:

int lowestRow = -1;
for (k = 0; k < array.length; k ++) {
   byte[] row = array[k];
   if (row[row.length - 1] == 0) {
       lowestRow = k;
       break;
   }
   if (row[row.length - 2] == 0) {
       lowestRow = k;
       //possibly look for all-zeroes, so not breaking
   }
}

Ответ 8

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

Ответ 9

Оптимизированная версия @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;
        }

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

Ответ 10

Найдите, какая строка имеет первое ненулевое значение в самом дальнем столбце. Если он двоичный, с MSB слева, а LSB справа - ответ, который начинается с большинства нулей.

Ответ 11

Я бы добавил это в качестве комментария к Джереми, если мог, потому что его решение в основном верное. Кроме того, мне нравится подход. Во многих случаях это будет намного быстрее, чем другие ответы. Возможна проблема. Если "Каждая строка сортируется". не означает, что все они сдвинуты вправо, но имеют некоторые другие последствия (я могу придумать пару следствий. Мне нужно больше от человека, задающего вопрос). Одна проблема... как насчет 0011 и 0010. Сортировка строк может означать, что алгоритм, который вы реализуете, уже используется. Алгоритм, указанный в его ответе, не может отличить их. Я бы сохранил индекс обоих ответов в массиве. Если длина массива равна 1, тогда у вас есть решение, в противном случае вам нужно еще больше отработать... просто мысль. Если кто-нибудь прочтет это, чтобы опубликовать комментарии к другим сообщениям, обратитесь к нему в комментарии к его сообщению. Это серьезная проблема, и было бы неприятно, если бы технически неверный ответ получил чек. Если мой комментарий будет добавлен, я полностью удалю свой ответ.

Ответ 12

Наименьшее число может быть 0, которое выглядит как (0000... 0000) или 1, которое выглядит как (0000... 0001).

Каждое большее число выглядит как (xxxx... xx11). Таким образом, вы должны проверить следующую последнюю цифру в каждой строке. Если это 0, то проверьте, равна ли последняя цифра 0. Если это наименьшее число. Если нет, то запомните номер строки и продолжайте искать строку с 0 на следующей последней цифре. Если вы его найдете, это будет наименьшее число. Если нет, первое найденное число будет наименьшим.

Это решение с шагом N + 1 (наихудший сценарий), который является сложностью O (N).

Ответ 13

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

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

Решение - это строка со значением 0. ИЛИ?

Ответ 14

Я написал алгоритм 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 )