python - 尝试获取列表列表中最大 y 值的总和([[x,y],[x,y]......)

Question

我正在尝试获取列表列表中每个“x”值的最大“y”之和。

示例:

l = [[1,29],[1,28],[2,30],[2,27]] 对于上面的列表，总和结果应为:29+30(x = 1 的最大 y 和 x = 2 的最大 y)

Answer 1

使用 dictionary累计每个x的最大y:

l = [[1, 29], [1, 28], [2, 30], [2, 27]]

d = {}
for x, y in l:
    if x not in d:
        d[x] = y
    else:
        d[x] = max(d[x], y)


res = sum(d.values())
print(res)

输出

59

另一种方法是使用 collections.defaultdict :

from collections import defaultdict

l = [[1, 29], [1, 28], [2, 30], [2, 27]]

d = defaultdict(lambda: float("-inf"))
for x, y in l:
   d[x] = max(d[x], y)


res = sum(d.values())
print(res)

输出

59

请注意，第二种方法之所以有效，是因为:

float("-inf") < x 

适用于任何整数x。两种方法的复杂度都是 O(n)。

更新

如果x的唯一值的数量很小(并且表示一组连续的索引)，第三种替代方法是使用列表而不是字典来存储最大y如下:

l = [[1, 29], [1, 28], [2, 30], [2, 27]]

cols = 2
d = [0 for _ in range(8)]  # here 8 is the number of columns in your game 
for x, y in l:
   d[x - 1] = max(d[x - 1], y)

res = sum(d)
print(res)

输出

59

请注意，此替代方案的工作原理是假设 y 值始终为正数(正如人们对俄罗斯方 block 游戏的列所期望的那样)。