algorithm - 两个和问题 - 有两个数组和突变

Question

我最近在编码测试中被问到这个问题，但无法以最佳方式完成。它是这样的:

You are given two arrays A, B and a list of queries - q. There are two types of queries - type 1: (1,i,x) where you set B[i] = x and type 2: (0, x) where you must calculate all pairs in A, B such that a[i] + b[j] == x. You must return a list of length equal to the number of type 2 queries. Keep in mind that after a type 1 query your B is now different.

example: A = [1,2], B = [3,4,5]. If the first query is (0, 5) you want to append the number 2 to your answer array because 1 + 4 = 5 and 2 + 3 = 5. (This is just the first query and there may be many more)

我的解决方案是存储 A 元素的计数器在哈希映射和每个类型 1 查询中是否会循环遍历 B 的元素并检查是否 x - b[i]是 A 的一个元素.
必须有更好的方法来做到这一点，但我不知道怎么做。

Answer 1

我可以看到 2 个优化，这可能会严重影响性能或根本不会影响性能，具体取决于问题设置。
让我们说:

q 是查询次数

a 是 A 中元素的数量

b 是 B

中元素的数量

m 是 A 或 B 中可能值的数量，例如如果 0 <= A[i], B[i] < 1000 那么 m = 1000

那么你的算法的时间复杂度为 O(b * q)。
下面是两个优化:

也将 B 的元素存储在哈希映射中。如果 m 比 b 或 a 小很多，这将非常有用。如果是这种情况，我们将得到 O(m * q)。

迭代较小的数组。如果您知道其中一个数组总是比另一个小得多，这将非常有用。所以我们会得到 O(min(a,b) * q)。

如果我们结合这两个优化，我们会得到 O(min(a, b, m) * q) 类似的东西(我知道你可能需要读取和打印这些值，但为了简单起见，我把它作为参数并返回):

public List<Integer> solve(int[] a, int[] b, int[][] queries) {
    List<Integer> ret = new ArrayList<>();
    Map<Integer, Integer> aMap = new HashMap<>();
    Map<Integer, Integer> bMap = new HashMap<>();
    for (int i : a)
        aMap.compute(i, (key, val) -> val == null ? 1 : val + 1);
    for (int i : b)
        bMap.compute(i, (key, val) -> val == null ? 1 : val + 1);
    for (int[] q : queries) {
        if (q[0] == 1) {
            int i = q[1];
            int x = q[2];
            bMap.compute(b[i], (key, val) -> val == 1 ? null : val - 1);
            b[i] = x;
            bMap.compute(x, (key, val) -> val == null ? 1 : val + 1);
        } else if (aMap.size() < bMap.size()) {
            ret.add(countPairs(aMap, bMap, q[1]));
        } else {
            ret.add(countPairs(bMap, aMap, q[1]));
        }
    }
    return ret;
}

private int countPairs(Map<Integer, Integer> a, Map<Integer, Integer> b, int x) {
    int count = 0;
    for (Map.Entry<Integer, Integer> entry : a.entrySet()) {
        if (b.containsKey(x - entry.getKey()))
            count += entry.getValue() * b.get(x - entry.getKey());
    }
    return count;
}

例如。如果问题是 a + b + m < c (一些常数)，这将是一个很好的解决方案。