找出差值大于或等于给定数的对的个数

Find number of pairs with difference larger than or equal to given number

本文关键字：大于      更新时间：2023-09-26

我有一个正整数数组/字典(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数组。

您可以获得数组的2个项目组合，然后根据差异进行筛选/减少。

在JavaScript中可以这样做;

Array.prototype.combinations = function(n){
  return this.reduce((p,c,i,a) => p.concat(n > 1 ? a.slice(i+1).combinations(n-1).map(e => (e.push(c),e))
                                                 : [[c]]),[]);
};
function getAcordingToDiff(a,d){
  return a.combinations(2)
          .reduce((p,c) => Math.abs(c[0]-c[1]) >= d ? (p.push(c),p) : p  ,[]);
}
var arr = Array(30).fill().map((_,i) => i+1); // array from [1,...,30]
console.log(JSON.stringify(arr))
console.log(JSON.stringify(getAcordingToDiff(arr,25))); // diff >= 25

解释:

所以上面代码的核心显然是Array.prototype.combinations函数。对于那些不熟悉JS的人来说，这只是我们在Array对象的原型下定义的一个普通函数(所以现在每个数组都可以访问这个函数，比如arr.combinations(n))。但是让我们使用一种更有表现力的语言，将上面的组合数组方法重构为一个泛型函数。

function combinations(a,n){
  var sa;
  return a.reduce(function(p,c,i,a){
                    if (n > 1) sa = combinations(a.slice(i+1), n-1).map(e => (e.push(c),e));
                    else sa = [[c]];
                    return p.concat(sa);
                  },[]);
}

所以你会注意到combinations(a,n)是一个递归函数，它接受数组a和项目计数n。它的工作原理是保持输入数组的第一项，并递归地调用自己，使用一个更短的项数组combinations(a.slice(i+1), n-1)，并减少一个项计数，直到n减少到1，在这种情况下，它开始使用输入数组中剩余的任何返回周期，每个项都被包装在一个数组sa = [[c]]中。

因此，在递归调用的返回周期中，我们取结果数组并将保留的第一个元素(记住->它是在保留输入数组的第一项的基础上工作的)压入返回数组的每个项(记住->…并且每一项都被包装在一个数组中，sa = [[c]])。

就是这样…你应该能自己弄清楚细节。

然而，在我们的应用程序中，我们得到一个数字数组，并要求只获得具有一定差异的2个项目组合。在这种特殊的情况下，我们不需要计算所有的组合，然后过滤它们。我们可以在构造组合的过程中这样做。随着所需的差值d变大，这将带来比事后过滤方法更大的收益，因为现在随着d变大，我们正在消除越来越多的两个项目组合，甚至在我们生成它们之前。和…让我们将代码硬连接为只处理2项，并将所有内容合并到一个函数中。性能结果如下:

function getCombosWithDiff(a, d, n = 2){
  var sa;
  return a.reduce(function(p,c,i,a){
                    if (n > 1) sa = getCombosWithDiff(a.slice(i+1), d, n-1).reduce((r,e) => Math.abs(e[0]-c) > d ? (e.push(c),r.push(e),r)
                                                                                                                 : r, []);
                    else sa = [[c]];
                    return p.concat(sa);
                  },[]);
}
var arr = Array(100).fill().map((_,i) => i+1);
 result = getCombosWithDiff(arr,89);
console.log(JSON.stringify(arr));
console.log(JSON.stringify(result));

就是这样。我已经尝试了上面的代码来列出两个项目组合，每个项目的差异大于10，从1000个项目的数组。在Chrome中需要5000毫秒，在FF中需要14000毫秒。然而，如上所述，d的diff值越大，所需时间越短。例如，使用diff 900的相同数组将在Chrome中解决仅1100msecs，而在FF中解决4000msecs。

你可以在这里测试和播放

创建一个包含1001个元素的整数数组a，初始化为0。生成随机整数，并为每个这样的整数增加相应的索引1。使用一些数学方法，您可以在不生成2,000,000个随机整数的情况下做到这一点，但它不值得这么复杂。

创建第二个包含1001个元素的整数B s.t。B[i] = a[0] +…+一个[我]

答案是B[i] * (2,000,000 - B[i+k-1])从i=0到1000-k的和

相关文章：