Python算法:在差分等于k的列表中搜索
Python算法:在差分等于k的列表中搜索
提问于 2016-06-24 19:59:54
number = [5,1,5,3,4]
k = 2返回差值等于k的计数。
cnt = 0
for i in nums:
for j in nums:
if i != j:
if i-j == k:
cnt += 1
return cnt你可以用O(N^2)来解
就复杂程度而言，能否以更快的方式进行呢？
它应该返回3，因为有三个求差等于2的情况。
5-3=2, 5-3=2, 3-1=2 回答 4
Stack Overflow用户
回答已采纳
发布于 2016-06-24 20:23:02
有一个简单的O(n * log(n))解决方案，其内存使用量为常数：
- 排序列表：
O(n * log(n)) - 对于排序列表中的每个元素
k，使用二进制搜索：<count of elements which is n> * O(log(n))在列表中搜索k + 2
因此，总体复杂性是O(n * log(n))。
注意，上面的步骤2可以使用两个指针将其转化为O(n)复杂性。
Stack Overflow用户
发布于 2016-06-24 20:06:47
简单的O(n)解决方案是使用hashtable ( python中的set完美地工作)创建索引，并为列表中的每个元素寻找一对。
但是由于我们关心相同项目的数量，我们应该使用dict或Counter来跟踪它们的数量。
from collections import Counter
number = [5,1,5,3,4]
k = 2
index = Counter(number)
for x in number:
if x + k in index:
for _ in range(0, index[x + k]):
print (x, x + k)Stack Overflow用户
发布于 2016-06-24 20:06:06
这个用的是发电机。它仍然是O(N^2)，但是速度应该是原来的两倍，因为你只检查一对的一侧。例如，如果数字是3，1，4，你只检查(3-1)，(3-4)和(1-4)，而不是(3-1)，(3-4)，(1-3)，(1-4)，(4-3)，(4-1)。
>>> sum(1 if abs(x - y) == k else 0
for n, x in enumerate(number)
for y in number[(n + 1):])
3更新
计数器可以用来缩小列表的大小。如果对于数字列表中的某个值m，存在一个数字n，以致于m + k = n，那么总计数就会随计数的乘积而增加。例如，对于数字= 1，1，2，3，3，3和k= 2，计数器将是{1: 2，2: 1，3: 3}，有六对:2x3 => (1，3) 6倍。可以使用get检索m + k的值(如果不存在，默认为零)。
我相信这是O(n)，因为时间尺度与数字的长度呈线性关系(尽管时间随着范围的增加而略有增加)。
from collections import Counter
import numpy as np时间
旧法
%%timeit np.random.seed(0); numbers = np.random.randint(1, 100, 10000)
sum(1 if abs(x - y) == k else 0
for n, x in enumerate(numbers)
for y in numbers[(n + 1):])
1 loops, best of 3: 17 s per loop新方法
%%timeit np.random.seed(0); numbers = np.random.randint(1, 100, 10000)
k = 10
count = 0
c = Counter(numbers)
for key in c:
count += c[key] * c.get(key + k, 0)
100 loops, best of 3: 3.83 ms per loop
# numbers are 100x larger.
%%timeit np.random.seed(0); numbers = np.random.randint(1, 100, 1000000)
k = 10
count = 0
c = Counter(numbers)
for key in c:
count += c[key] * c.get(key + k, 0)
100 loops, best of 3: 380 ms per loop 页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/38021217
复制相关文章
相似问题
腾讯云开发者
