时间戳

首页 > 解决方案 > 如何在 O(n) 的列表中找到最小正整数？

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

问题描述

我正在尝试在 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]]

IE。输出应该是 1 但它仍然是 10 感觉我很接近所以任何帮助将不胜感激！

标签： pythonbig-o

解决方案

一个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

推荐阅读