给定一个数组和某个值 X，找到满足以下条件的对的数量：i < j , a[i] = a[j] and (i * j) % X == 0
Array size <= 10^5
我想这个问题有一段时间了，但只能想出蛮力解决方案（通过检查所有对），这显然会超时[O(N^2) time complexity]
还有更好的方法吗？
首先，为每个不同的搜索结构存储单独的搜索结构A[i]当我们迭代时。
i * j = k * X
i = k * X / j
Let X / j是某个分数。自从i是一个整数，k将是以下形式m * least_common_multiple(X, j) / X, where m is natural.
示例1：j = 20, X = 60:
lcm(60, 20) = 60
matching `i`s would be of the form:
(m * 60 / 60) * 60 / 20
=> m * q, where q = 3
示例2：j = 6, X = 2:
lcm(2, 6) = 6
matching `i`s would be of the form:
(m * 6 / 2) * 2 / 6
=> m * q, where q = 1
接下来，我将考虑如何有效地查询任意自然数排序列表中某个数字的倍数的个数。一种方法是散列每个因子的除数频率i我们添加到搜索结构中A[i]。但首先考虑i as j并将除数计数添加到结果中q已经存在于哈希映射中。
最后进行暴力测试的 JavaScript 代码：
function gcd(a, b){
return b ? gcd(b, a % b) : a;
}
function getQ(X, j){
return X / gcd(X, j);
}
function addDivisors(n, map){
let m = 1;
while (m*m <= n){
if (n % m == 0){
map[m] = -~map[m];
const l = n / m;
if (l != m)
map[l] = -~map[l];
}
m += 1;
}
}
function f(A, X){
const Ais = {};
let result = 0;
for (let j=1; j<A.length; j++){
if (A[j] == A[0])
result += 1;
// Search
if (Ais.hasOwnProperty(A[j])){
const q = getQ(X, j);
result += Ais[A[j]][q] || 0;
// Initialise this value's
// search structure
} else {
Ais[A[j]] = {};
}
// Add divisors for j
addDivisors(j, Ais[A[j]]);
}
return result;
}
function bruteForce(A, X){
let result = 0;
for (let j=1; j<A.length; j++){
for (let i=0; i<j; i++){
if (A[i] == A[j] && (i*j % X) == 0)
result += 1;
}
}
return result;
}
var numTests = 1000;
var n = 100;
var m = 50;
var x = 100;
for (let i=0; i<numTests; i++){
const A = [];
for (let j=0; j<n; j++)
A.push(Math.ceil(Math.random() * m));
const X = Math.ceil(Math.random() * x);
const _brute = bruteForce(A, X);
const _f = f(A, X);
if (_brute != _f){
console.log("Mismatch!");
console.log(X, JSON.stringify(A));
console.log(_brute, _f);
break;
}
}
console.log("Done testing.")
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
