最快的算法可以选择数字对

Question

问题:给定N个整数[N <= 10 ^ 5],计算具有K差异的整数对.[K> 0和K <1e9].N个整数中的每一个将大于0且至少K远离2 ^ 31-1(一切都可以用32位整数完成).

第一行包含N&K(整数).第二行包含N个集合.确保所有N个数字都是不同的.

现在问题来自hackerrank.我得到了一个问题的解决方案,但它不满足所有样本测试用例的时间限制.我不确定是否可以使用其他算法,但我没有想法.如果有人花一点时间检查我的代码并给出一两个提示,我们将非常感激.

temp = input()
temp = temp.split(" ")
N = int(temp[0])
K = int(temp[1])
num_array = input()
num_array = num_array.split(" ")
diff = 0
pairs= 0
i = 0
while(i < N):
    num_array[i] = int(num_array[i])
    i += 1
while(num_array != []):    
    j = 0
    while(j < (len(num_array)-1)):
        diff = abs(num_array[j+1] - num_array[0])
        if(diff == K):
            pairs += 1
        j += 1
    del num_array[0]
    if(len(num_array) == 1):
        break
print(pairs)

Answer 1

您可以按照以下步骤在近似线性时间内执行此操作:

所以,O(n)解决方案:

1. 对于每个数字x,将其添加到哈希集H [x]
2. 对于每个数字x,检查xk是否在H中,如果是 - 添加1来回答

或者在O(nlgn)中使用一些平衡结构(如基于树的集合)

这个解决方案基于整数是不同的假设,如果它们不是你需要存储元素被"添加到集合"的次数而不是添加1来回答 - 添加H [x]*H的乘积[ X + k]的

所以一般来说你带一些HashMap H"默认值0"

1. 对于每个数字x更新地图:H [x] = H [x] +1
2. 对于每个数字x加上回答H [x]*H [xk](你不必检查它是否在地图中,因为如果不是,H [xk] = 0)

再次 - 使用hash-map的解决方案是O(n)并使用树映射O(nlgn)

给定一组numbesr A和数字k(不同数字的解):

H=set()
ans=0
for a in A: 
  H.add(a)
for a in A: 
  if a-k in H: 
    ans+=1
print ans

或更短

H=set(A)
ans = sum(1 for a in A if a-k in H)
print ans