检查列表是否有最小列表

Question

我有一个列表 S，里面包含了多个子列表。所有的子列表大小都一样，里面的内容都是数字。

我们说 S 有一个最小值，如果在 S 中存在一个子列表，它的每个数字都不大于其他子列表中对应位置的数字。

举个例子，

S = [[4, 5, 6], [3, 6, 9], [1, 4, 6], [2, 5, 8]] 这个列表有一个最小值，因为 [1, 4, 6] 里的数字都比其他子列表中相同位置的数字要小。

而 S = [[4, 5], [3, 6]] 这个列表就没有最小值。

有没有办法在不检查所有可能的子列表组合的情况下找到这个最小值呢？

Answer 1

我建议你先创建一个每个位置的最大值列表，然后把每个子列表和这些最大值进行比较：

S = [[4, 5, 6], [3, 6, 9], [1, 4, 6], [2, 5, 8]]

out = [max(l) for l in zip(*S)]
out = next((l for l in S if all(a < b for a, b in zip(l, out))), None)

print(out)

输出结果是：

[1, 4, 6]

---

对于 S = [[4, 5], [3, 6]]，输出结果是：

None

Answer 2

你做得很好，这其实是一个很好的总结，说明了你可以怎么处理一个单一的数值。

首先，遍历一遍列表，找出每个位置的最小值。

然后，再遍历一遍列表，看看哪一行的值和这些最小值匹配。

def minimumList( S ):
   N = len( S[0] )
   minima = S[0].copy()
   for row in S:
       for i, v in enumerate( row ):
           if v < minima[i]: minima[i] = v
   for row in S:
       if row == minima: return True, row
   return False, []


print( minimumList( [[4, 5, 6], [3, 6, 9], [1, 4, 6], [2, 5, 8]]) )
print( minimumList( [[4, 5], [3, 6]] ) )

输出结果：

(True, [1, 4, 6])
(False, [])

Answer 3

这里有一个解决方案：

s = [[4, 5, 6], [3, 6, 9], [1, 4, 6], [2, 5, 8]]
min_list = [min(x) for x in zip(*s)]
if min_list in s:
    print(f"Min list found: {min_list}")
else:
    print("Min list not found")

输出结果：

Min list found: [1, 4, 6]

解释

首先，我们计算出一个最小列表，叫做 min_list，然后检查这个列表是否存在于 s 中。那么，下面的内容是怎么工作的呢？

min_list = [min(x) for x in zip(*s)]

我们先来看一下 zip 在 s 上的效果：

>>> list(*zip(s))
[(4, 3, 1, 2), (5, 6, 4, 5), (6, 9, 6, 8)]

在这个例子中，zip 会返回一个包含三个子列表的列表。第一个子列表包含所有的第一个元素（或者用提问者的说法：条目）。第二个子列表包含所有的第二个元素，以此类推。

接着，我们对这些子列表使用 min() 函数，最终得到最小列表 min_list。