java - 交换搜索算法

Question

我有一个包含 n 个整数的数组 A。我还有一个由 k (k < n) 个整数组成的数组 B。我需要的是数组 A 中出现在数组 B 中的任何整数都增加 3。

如果我采用最明显的方式，我会得到 n*k 的复杂性。数组 A 不能（一定不能）排序。

有没有更有效的方法来实现这一目标？

Answer 1

有没有更有效的方法来实现这一目标？

是：将 的元素B放入HashSet. 循环A，如果您所在的元素包含在集合中，则将其增加 3。这将具有 O(n + k) 复杂度。

例如：

Set<Integer> bSet = new HashSet<>(B.length);

for (int a : B)  // O(k)
    bSet.add(a);

for (int i = 0; i < A.length; i++) {  // O(n)
    if (bSet.contains(a[i]))
        a[i] += 3;
}

Answer 2

如果您的整数在您可以创建的范围内并以最大值的长度排列（例如0 <= A[i] and B[i] <= 65535），那么您可以这样做

boolean [] constains = new boolean[65535];
for (int i = 0; i < k; i++){
    constains[B[i]] = true;
}

for (int i = 0; i < n; i++){
    if (constains[A[i]]){
        A[i] += 3;
    }
}

这是 O(n + k)

Answer 3

如果数组 B 可以排序 - 那么解决方案很明显，对其进行排序，然后您可以将“包含”优化为 log2(K)，因此您的复杂度将为 N*log2(k)

如果你不能对数组 B 进行排序 - 那么唯一的事情就是直接 N*K

更新

真的忘记了位掩码，如果你知道你只有 32 位整数，并且有足够的内存 - 你可以存储巨大的位掩码数组，“添加”和“包含”总是 O(1)，但当然需要仅用于非常特殊的性能优化