代码之家 › 专栏 › 技术社区 › Marchi

计算具有继承者的元素数的最佳方法

list arrays python

Marchi · 技术社区 · 6 年前

给定一个n个元素的列表,我想计算元素的数量,i,这样它们的后继元素i+1也在列表中。

这是一个朋友给我的问题,我找不到元素值高达100000000的大N(100000)的最佳解决方案。下面是我当前使用随机生成的列表的方法,这需要很长的时间。

import random
temp = random.sample(range(1000000000),random.randint(2,100000))
total_sum = 0
for i in range(len(temp)):
    if (temp[i]+1) in temp:
        total_sum+=1
print(total_sum)

1 回复 | 直到 6 年前

Dani Mesejo 6 年前

使用A set :

import random
random.seed(42)

temp = random.sample(range(1000000000), random.randint(2, 100000))

s = set(temp)
total_sum = sum(e + 1 in s for e in temp)
print(total_sum)

产量

集合中的查找时间为 O(1) 而不是一个列表 o(n) . 使用集合的方法是 o(n) ,您当前的实现是 O(n ^ 2) .

推荐文章

Dave · 如何在for循环中修改列表值

5 月前

geoscience123 · 如何计算R中一个表列与另一个数据帧的匹配数?

5 月前

matteo panaro · 向列表中添加项目

6 月前

Bioinfotec · 如何在R中将两个嵌套列表合并为一个列表?

6 月前

Jeffrey Van Laethem · 获取两个列表之间的所有元组排列

6 月前

Pernoctador · Python映射可以复制吗?我需要参考地图

6 月前

Bogaso · 从列表中返回与模式匹配的元素

6 月前

Daniel · 我有一组要排除的单词,我想检查输入的每个新单词是否完全包含在另一个单词中。我该怎么做?

6 月前

Tom Hunter · Excel验证列表中的条目

7 月前

Estrobelai · Python:数组中价格高于平均值的所有项目

10 月前