交换搜索算法

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

如果数组B可以排序-那么解决方案是显而易见的，排序它，然后你可以优化“包含”为log2(K)，所以你的复杂性将是N*log2(k)

如果不能对数组B进行排序，那么唯一要做的就是直接进行N*K排序

更新

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

Answer 3

如果您的整数在您可以创建的范围内并使用最大值的长度进行数组(例如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)