代码之家 › 专栏 › 技术社区 › 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) .

推荐文章

Toniq · javascript为php保存多维数组

1 年前

Jannis · Java中数组的怪异行为

1 年前

callum · 如何识别数组中与给定序列不匹配的元素?

1 年前

Gamerboi677 _YT · 如果玩家触摸了某个部分,如何将玩家名称添加到数组中。-Roblox-Lua编码

1 年前

at. · 在一行中创建任意大小的JavaScript/TypeScript 2d数组

1 年前

Rakis Friski · Javascript Spread运算符混淆行为

1 年前

tenfour · 如何使用数组元素的索引初始化数组元素

2 年前

Guillaume · 使用操作从Python列表创建numpy数组

2 年前

maxMas · Swift 5:为什么会出现索引超出范围错误?

2 年前

Sarah Workman · 尝试比较用javascript编程添加的字符串的值

2 年前