5

问题：给定 N 个整数 [N<=10^5]，计算相差 K 的整数对的总数。[K>0 和 K<1e9]。N 个整数中的每一个都将大于 0，并且距离 2^31-1 至少为 K（一切都可以用 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)
4

2 回答 2

5

您可以按照以下过程在近似线性的时间内完成此操作：

因此，O(n) 解决方案：

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

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

该解决方案基于整数是不同的假设，如果不是，您需要存储元素被“添加到集合”的次数，而不是添加 1 来回答 - 添加 H[x]*H[ 的乘积x+k]

所以一般来说，你会使用一些带有“默认值 0”的 HashMap H

  1. 对于每个数字 x 更新映射：H[x] = H[x]+1
  2. 对于每个数字 x 添加答案 H[x]*H[xk] （您不必检查它是否在地图中，因为如果不在，则 H[xk]=0 ）

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

所以给定一组数字 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
于 2013-10-27T14:15:48.633 回答
2

使用字典（哈希图）。

第 1 步：用数组中的所有条目填充字典 D。第 2 步：计算字典中所有 A[i] + k 的出现次数。

Dictionary<int> dict = new Dictionary<int>();
foreach (int n in num_array) do dict.Add(n);
int solitions = 0;
foreach (int n in num_Array) do 
  if dict.contains(n+k) 
    solutions += 1;

填充字典是 O(1)，搜索也是 O(1)。对数组中的每个元素执行此操作是 O(n)。这是尽可能快的。

对不起，你必须把它翻译成 python。

编辑：与前一个想法相同。很抱歉发布重复。我想删除我的副本为时已晚。

于 2013-10-27T14:28:53.063 回答