python - Python 字典的求和值(时间/空间复杂度)

Question

我正在尝试解决以下问题:

给定出生日期和死亡日期列表，找出在世人数最多的年份。

到目前为止，这是我的代码:

b = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
d = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates

year_dict = {} # populates dict key as year, val as total living/dead
for birth in b:
    year_dict.setdefault(birth,0) # sets default value of key to 0 
    year_dict[birth] += 1 # will add +1 for each birth and sums duplicates
for death in d:
    year_dict.setdefault(death,0) # sets default value of key to 0
    year_dict[death] += -1 # will add -1 for each death and sums duplicates

以下代码返回:

{1791: 1, 1796: 1, 1691: 1, 1907: 1, 1999: 1, 2001: 1, 1800: -1, 1803: -1, 1692: -1, 1852: -1, 1980: -1, 2006: -1}

现在我正在寻找一种创建运行总和的方法，以找出哪一年的人口最多，例如:

Image of desired result

如我们所见，根据给定的数据集，结果显示 1796 年的人口最多。我在获取需要获取每个键值并将其与先前值相加的运行总和部分时遇到问题。我尝试了几种不同的循环和枚举，但现在卡住了。找到解决此问题的最佳方法后，我将创建一个函数以提高效率。

如果考虑到时间/空间复杂性，有更有效的方法，请告诉我。我正在尝试学习 python 的效率。非常感谢您的帮助!!!

Answer 1

您是否希望使用特定的数据结构来存放结果？我得到了与打印到终端的 imgur 链接相同的结果。不过，将其写入字典并不难。

from collections import OrderedDict

b = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
d = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates

year_dict = {} # populates dict key as year, val as total living/dead
for birth in b:
    year_dict.setdefault(birth,0) # sets default value of key to 0 
    year_dict[birth] += 1 # will add +1 for each birth and sums duplicates
for death in d:
    year_dict.setdefault(death,0) # sets default value of key to 0
    year_dict[death] += -1 # will add -1 for each death and sums duplicates

year_dict = OrderedDict(sorted(year_dict.items(), key=lambda t: t[0]))
solution_dict = {}

total = 0
print('year net_living running_sum')
for year in year_dict:
    total += year_dict[year]
    solution_dict.update({year:{'net_living': year_dict[year],
                                'running_sum': total}
                                })
    print('{} {:4} {:10}'.format(year, year_dict[year], total))

输出:

year net_living running_sum
1691    1          1
1692   -1          0
1791    1          1
1796    1          2
1800   -1          1
1803   -1          0
1852   -1         -1
1907    1          0
1980   -1         -1
1999    1          0
2001    1          1
2006   -1          0

solution_dict 的输出

{
1691: {'net_living':  1, 'running_sum':  1},
1692: {'net_living': -1, 'running_sum':  0},
1791: {'net_living':  1, 'running_sum':  1},
1796: {'net_living':  1, 'running_sum':  2},
1800: {'net_living': -1, 'running_sum':  1},
1803: {'net_living': -1, 'running_sum':  0},
1852: {'net_living': -1, 'running_sum': -1},
1907: {'net_living':  1, 'running_sum':  0},
1980: {'net_living': -1, 'running_sum': -1},
1999: {'net_living':  1, 'running_sum':  0},
2001: {'net_living':  1, 'running_sum':  1},
2006: {'net_living': -1, 'running_sum':  0}
}