在 O(n*log(n)) 内查找具有给定总和和乘积的一对数组元素

Question

设 A 是一个由 n 个正整数组成的数组，并且 ka 是给定的整数。

我正在寻找一种算法来查找数组中是否存在一对元素，使得 A[i] * A[j] == k 和 A[i] == A[j] + k。如果存在这样的一对，算法应该返回它们的索引。

这是一个家庭作业，我们被告知有一个 O(n*log(n)) 解决方案。

Answer 1

我首先想到的是：

Make a Map<Integer, Integer>

for each number a in A:
   if (k / a) is a key in the HashMap:
      output the index of a, and HashMap.get(k/a)
   else
      HashMap.add(a, indexof(a))

遍历数组的时间复杂度为 O(n)，在 Map 中查找键的时间复杂度为 O(log n)（假设您使用 TreeMap，在最好的情况下 HashMap 可能会更好）但在最坏的情况下更糟）

编辑：我想这只能回答a）但你明白了

Answer 2

Sort the array. Also build a permuted index array by initializing an auxiliary array to 0, 1, 2 ... n and swapping indices every time you swap elements in the array, Time O(nLog(n))

for each element a[i] in array, Time O(n)

  Binary Search for (a) k / a[i] or (b) a[i] - k, if found, return index j from permuted index array, Time O(log(n))

Answer 3

这是 Graphics Noob 的解决方案，有些澄清。

而且，它更像是 O(N)（假设哈希不会让我们失败），而不是 O(N*log(N))。

Result findMultiplicationIndices(int[] A, int[] B, int k)
{
    HashMap<Integer,Integer> aDivisors = new HashMap<Integer,Integer>();
    for(int i=0;i<A.length;i++)
    {
        int a = A[i];
        if(a!=0)
        {
            int d = k/a;
            if(d*a == k) 
                aDivisors.put(d, i);
        }
    }
    for(int i=0;i<B.length;i++)
    {
        Integer ai = aDivisors.get(B[i]);
        if(ai != null)
            return new Result(ai, i);
    }
    return null;
}

Answer 4

使用nlog(n)排序
然后遍历数组
对于每个索引，我计算 A[j] 需要什么才能满足方程
检查数组中是否存在这样的值

O(nlogn) + O(N)*O(logn)
=O(nlogn)

Answer 5

如果 k 是固定的，则有有限多个整数 x, y 使得 x*y = k。
对于每个因子 (x,y)，迭代列表以确定 A[i] = x 或 A[i] = y。
总运行时间 = O(n) * k 的 # 个因子 = O(n) （确定性地，不是关于散列的假设）

该问题表明 A[i] 都是正数，因此 k 可以有限地分解 x + y = k也有很多方法，所以 O(n) 也是如此。