javascript - 查找差值大于或等于给定数字的对数

Question

我有一个正整数数组/字典(HashMap)。我需要找到绝对差值大于或等于给定数 K 的对数。

import random
import time

#given number
k =  4

# List of 2,00,000 random numbers in range 0-1000
strength = [random.randrange(0,1000) for x in range(200000)]  
strength.sort()

# start clock
start1 = time.clock()

n = len(strength)

# count keeps track of number of pairs found
count = 0

for x in range(n):
    for y in range(x,n):

        if abs(strength[x] - strength[y]) >= k:
            # if found, all number from this point to the end will satisfy
            count += n-y
            # So no need to go to the end
            break

end1 = time.clock()
print(count)
print(end1-start1)

我找到的所有答案都是针对小于或等于给定数字的对。

我需要找出绝对差值大于或等于给定数 K 的对数。

Answer 1

注意对的总数是n * (n - 1)/2，所以如果你能找到差值小于K的对数，差值大于 K 的对数仅为 n * (n - 1)/2 - num_pairs_with_diff_less_than_K

您提供的解决方案也是正确的(并且有据可查)。如果您的问题是如何使其适应您的情况，那么您需要做的就是使用 HashMap 的值(排序)而不是 strength 数组。