Блог

Я пытаюсь написать программу на python, которая использует список, содержащий столько внутренних списков, сколько длина внешнего списка. Например,

 L = [[-10, -9,    99,   100],
     [ -6, -3,   100,   101],
     [ -1,  0,  1000,  1010],
     [ -1, 10, 10000, 24852]]
  

и он выводит наименьшее положительное целое число. Выводит значение -1, если все элементы отрицательные или 0. Результат для приведенного выше списка будет равен 10. Элементы также всегда сортируются в порядке возрастания, поэтому и строки, и столбцы сортируются в порядке возрастания. Это означает, что если вы посмотрите на любую строку или любой столбец, они будут отсортированы слева направо и сверху вниз соответственно.

Проблема в том, что я должен делать это с эффективностью O (n) (n относится к длине внешнего списка), но каждое решение, которое я придумываю, включает вложенные циклы, и, таким образом, эффективность становится O (n ^ 2).

Как я могу добиться этого с эффективностью O (n) в python?

Редактировать: я написал следующий код, который работает для некоторых случаев, но не работает для других

 def min_positive(L): 
i = 0
n = len(L)
j = len(L) - 1
min_pos = L[0][j]
while ( i < n and j >= 0 ): 
    if (L[i][j] < min_pos and L[i][j] > 0): 
        min_pos = L[i][j]
    if (L[i][j] >= min_pos): 
        j = j - 1 
    i = i   1
if min_pos <= 0:
    min_pos = -1 
return min_pos
  

Это работает для следующего списка

 L = [[-10, -9,    99,   100],
 [ -6, -3,   100,   101],
 [ -1,  0,  1000,  1010],
 [ -1, 10, 10000, 24852]]
  

но не работает для списка

 L = [[-10, -9,    99,   100],
     [ -6, -3,   100,   101],
     [ -1,  0,  1000,  1010],
     [ 1, 10, 10000, 24852]]
  

ie. вывод должен быть 1, но все равно 10
Чувствую, что я близок, поэтому буду признателен за любую помощь!

Это наихудший вариант O(M N) решения, где M — количество строк, а N — количество столбцов.

 L = [[-10, -9,    99,   100],
     [ -6, -3,   100,   101],
     [ -1,  0,  1000,  1010],
     [ -1, 10, 10000, 24852]]

def get_least_positive(list_of_lists):
    minimum = float("inf")

    # start from top right
    row = 0
    column = len(list_of_lists[0]) - 1

    # follow the staicase
    while row < len(list_of_lists) and column >= 0:
        elem = list_of_lists[row][column]
        if elem > 0:
            minimum = min(minimum, elem)
            column -= 1
        else:  # found Negative, go to next row.
            row  = 1

    return minimum if minimum != float('inf') else -1


print(get_least_positive(L))

  

Идея O (n) состоит в том, чтобы начать с верхнего правого угла, двигаться влево, когда вы находитесь на положительном значении, и двигаться вниз в противном случае. Для квадратного массива это посещает не более 2 * n — 1 индексов, потому что алгоритм никогда не возвращается. Подписка на список равна O (1), поэтому мы имеем линейную временную сложность и постоянную пространственную сложность.

 def min_linear(L):
    n_rows = len(L)
    n_cols = len(L[0])
    row, col = 0, n_cols - 1  # start a the top-right corner
    best = L[-1][-1]  # initialized to the maximum element
    if best <= 0:
        # no positive elements
        return -1
    while col >= 0 and row < n_rows:
        val = L[row][col]
        if val > 0:
            best = min(val, best)
            col -= 1  # move left
        else:
            row  = 1  # move down
    return best
  

Я могу дать некоторую основную идею:

1. начните с нижнего правого

поскольку оно отсортировано как по строке, так и по столбцу, это означает, что нижний правый самый большой, а если нижний правый отрицательный, то остальные значения отрицательны.

2. создайте решение для обхода пути

Это означает, что вы хотели бы идти вниз (по убыванию), пока не встретите отрицательное значение, которое затем перемещается в другом направлении. Утилита преимущество возрастания в том, что вы можете перейти к минимальному pos, не проверяя средние элементы, потому что они явно больше. Поступая таким образом, вы также можете пропустить отрицательное значение.