我有一个正整数数组/字典(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 的对数。
最佳答案
注意对的总数是n * (n - 1)/2
,所以如果你能找到差值小于K
的对数,差值大于 K
的对数仅为 n * (n - 1)/2 - num_pairs_with_diff_less_than_K
您提供的解决方案也是正确的(并且有据可查)。如果您的问题是如何使其适应您的情况,那么您需要做的就是使用 HashMap
的值(排序)而不是 strength
数组。
关于javascript - 查找差值大于或等于给定数字的对数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40347423/