交换搜索算法

Question

我有一个包含n个整数的数组A。我还有一个包含k个整数的数组B（k < n）。我需要的是将数组A中出现在数组B中的任何整数增加3。

如果我采用最明显的方法，时间复杂度为n*k。 数组A不能（也必须不）排序。

有更有效的方法实现这个吗？

- Karlovsky120

---

也许，整数（n）的范围是什么。 - Omar Mainegra

@omainegra 我认为他们相当生气。 - Snakes and Coffee

数组A能否被排序？ - libik

数组A不能被排序。我的意思是，当然它可以被排序，它是一个整数数组，但这会破坏程序的其他部分。 - Karlovsky120

使用var newArray = new int[A.length]; System.arrayCopy(A,0,newArray,0,A.length)将A复制到newarray。现在，您可以很好地对A的副本进行排序。仅因为您无法对A进行排序并不意味着您无法对数据进行排序。 - Mike 'Pomax' Kamermans

A和B的大小范围是多少，B能被排序吗？ - גלעד ברקן

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;
}

- arshajii

---

这是错误的，使用B创建HashSet的复杂度为O(klogk)，遍历A的复杂度为O(nlogk)，因此总复杂度为O(nlogk + klogk)，即O(logk(n+k))。 - libik

@libik 这不是真的。将元素添加到 HashSet 中是一个常数时间的过程。包含测试也是 O(1)，增量也是如此。因此，第二个循环在 n 中是线性的，而第一个循环在 k 中是线性的。因此，总体复杂度 是 O(n + k)。 - arshajii

当然不是。只有当你拥有无限的内存时，才能在常数时间内工作。否则不行。实际上哈希意味着，在平均情况下，您的问题会乘以当前哈希差异的数量。因此，复杂度被可能的哈希解决方案的数量除。真正的哈希“包含”的值是n/k，其中k是一个大常数，仍然是常数。对于小实例，k > n，所以它几乎可以在常数时间内工作。（但是如果你运气不好，你可能会达到O(n)的复杂度，但这种情况太小了，不足以成为问题） - libik

bSet.contains的复杂度不是1，而.add也不是1。 - Iłya Bursov

另外，我请求您重新考虑您的负评，因为我不认为其背后的原因是合理的。 - arshajii

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)的时间复杂度

- Omar Mainegra

Answer 3

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

如果无法对数组B进行排序 - 那么唯一的方法是直接使用N * K

更新

真的忘记了位掩码，如果您知道只有32位整数，并且具有足够的内存 - 您可以存储巨大的位掩码数组，其中“添加”和“包含”始终为O（1），但当然仅适用于非常特殊的性能优化。

- Iłya Bursov