python - 如何在 O(n) 的列表列表中找到最小正整数？

Question

我正在尝试用 python 编写一个程序，该程序使用一个列表，该列表包含与外部列表长度一样多的内部列表。例如，

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

它输出最小的正整数。如果所有元素均为负数或 0，则输出 -1。上面列表的输出将为 10。元素也始终按升序排序，因此行和列均按升序排序。这意味着如果您查看任何行或任何列，它将分别从左到右和从上到下排序。

问题是我必须以 O(n) 效率(n 指的是外部列表的长度)执行此操作，但我提出的每个解决方案都涉及嵌套循环，因此效率变为 O(n^2)。

如何在 python 中实现 O(n) 效率？

编辑:我编写了以下代码，它适用于某些情况但不适用于其他情况

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]]

即。输出应该是 1 但它仍然是 10感觉我很亲近，所以我们将不胜感激!

Answer 1

这是最坏的情况，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))