Python字典的值求和（时间/空间复杂度）

Question

Python字典的值求和（时间/空间复杂度）

pythonpython-3.xdictionarytime-complexityspace-complexity

3

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

给定出生日期和死亡日期列表，找到最多人活着的年份。

以下是我的代码：

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}

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

所需结果的图像

正如我们所看到的，根据给定的数据集，结果显示1796年有最多的人口。我无法得到运行总和部分，它需要将每个键值与前一个值相加。我尝试了几个不同的循环和枚举，但现在卡住了。一旦我找到解决这个问题的最佳方法，我就会创建一个函数来提高效率。

如果有更有效的方法考虑时间/空间复杂度，请告诉我。我正在尝试学习使用Python实现效率。非常感谢您的帮助！！！

- HackPy

1

这些年背后的结构是什么？第六个在出生之前21年就去世了吗？ - Klaus D.

出生于2001年，逝世于1980年。短暂的生命，倒退着老去。 - Patrick Artner

我们去的地方不需要倒退。 - duhaime

这些集合故意是无序的，因为它们不需要有序。如果你从大局来看，为了找到解决方案，我们并不关心某个人活得长短，唯一影响解决方案的是出生/死亡发生的时间。但是没错，-21的寿命确实很短 :) - HackPy

2个回答

1

我会使用 pandas，并利用它的 DataFrame 对象：

创建一个包含人们出生年份和死亡年份的数据框：

born = [1791, 1796, 1691, 1907, 1999, 2001, 1907] # birth dates
died = [1800, 1803, 1692, 1907, 1852, 1980, 2006] # death dates
people = pd.DataFrame({'born': born, 'died': died} for born, died in zip(born, died))

创建一个包括第一个出生日期和最后一个死亡日期之间所有年份的数据框：

years = pd.DataFrame(index=np.arange(people['born'].min(), people['died'].max() + 1))

找出这些年份每年存活的总人数：

for year in years.index:
    num_living = ((year > people['born']) & (year < people['died'])).sum()
    years.loc[year, 'total_living'] = num_living

调用years.tail()的结果如下：

    total_living
2002    1.0
2003    1.0
2004    1.0
2005    1.0
2006    0.0

从那里开始，您只需在“total_living”列上执行一个简单的argmax即可。

需要明确的是，我假设人们在出生后死亡，因此永远不会有负数的存活人数。

- PMende

我喜欢Pandas，并且已经用它来编辑csv/excel文件。实际上，我有一个类似这样的解决方案，但是想用标准库再写一个。 - HackPy

如果你想要高效的话，我可以告诉你，在这个任务上标准库比起pandas会慢得多。 - PMende

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Sean · Accepted Answer

您是否想要使用特定的数据结构来存储结果？我得到了与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

解决方案字典的输出

{
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}
}