需要优化算法- 数组

Question

我们有一个大小为N的整数数组A。给定另一个包含索引的数组B，其中B的大小<= N且0<=B[i]<=N-1。

现在我们必须从数组A中删除所有位于位置B[i]的元素。

因此，删除意味着我们也要移动数组A中的元素。

有人能帮我找到这个问题的O(n)解决方案吗？并且尽可能使用O(1)空间。

我脑海中首先想到的解决方案是遍历数组B并按顺序删除A中的元素（包括移动），但它的时间复杂度是O(n^2)。

- learner

---

B的元素是否按某种顺序排序？如果您还在移动A，则B中元素的顺序很重要。 - SubmittedDenied

你对这些数字有任何限制吗？我的意思是，你能使用一些特殊值来标记某些元素为“已删除”吗？如果可以的话，这将是一个简单的问题。 - Kiril Kirov

@Kiril，不允许将元素标记为已访问/已删除 :( - learner

@SubmittedDenied，B数组中的元素不需要排序。 - learner

嗯，不允许使用O(1)空间和标记。而且更重要的是，B没有排序。我不确定这是否可能。 - Kiril Kirov

Answer 1

与iliaden的解决方案类似，不过你可以在原地删除已删除元素。

int[] a = 
int[] b = 
int nullValue = 
for(int i: b) a[i] = nullValue;
int j=0;
for(int i=0; i < a.length; i++) {
    if(a[i] != nullValue)
       a[j++] = a[i];
}
// to clear the rest of the array, if required.
for(;j<a.length;j++)
   a[j] = nullValue;

注意：a 的长度不会更短，但它避免了创建更多的空间。'j' 将拥有 a 中有效条目的数量。

- Peter Lawrey

---

太好了，O(n)时间复杂度和O(1)空间复杂度。完美。非常感谢 :) - learner

我认为这已经是最好的了，改变数组的大小通常需要O(n)的内存（创建新的数组，复制所有内容）。也许值得遍历剩余的N-j个元素，并在其中写入空值。 - SubmittedDenied

这个解决方案取决于A的内容具有某种空值。这通常不是这种情况。如果没有空值，您必须单独维护有关已删除哪些元素的信息，在某种位向量中。上面的第二个循环只是std::remove_if的一个效率较低的版本。 - James Kanze

@James，OP已经发帖表示他相信可以进行O（1）内存分配，这意味着应该在不分配与大小成正比的额外内存的情况下完成。根据我的经验，在业务逻辑中，始终存在null值。我不认为std::remove_if比第二个循环更有效率。（现在我把第二个循环移出了 ;) - Peter Lawrey

根据我的经验，空值并非总是可能存在的；这就是为什么发明了Fallible类（或boost::optional或Maybe）。但这取决于应用程序以及他在数组中存储的东西的类型（他没有告诉我们）。如果没有空值，我认为没有额外的内存解决方案；你必须在某个地方存储额外的信息。至于remove_if，看看它；通常，它使用std::find_if来查找开始复制的位置，从而避免了一些不必要的自我赋值。 - James Kanze

Answer 2

在O(n)的空间中，您可以执行以下操作：

1. 遍历数组A，在b[i]处删除每个元素（不进行移位，O(n)）

2. 创建一个新数组C，将所有非空元素从A顺序复制到C中（同样是O(n)）

3. 返回数组C或将其复制回已清除的数组A（O(n)）。 因此，您可以在O(n)时间和O(n)空间内完成此操作。

- iliaden

---

谢谢回复。这个方法可行，但我想找一个空间复杂度为O(1)，时间复杂度为O(n)的解决方案。 - learner

Answer 3

两个明显的解决方案：在开始之前按相反的顺序对B进行排序，这样您总是删除最高索引（因此永远不会移动已删除的元素），或者遍历B以创建要删除的元素的位图（然后以相反的顺序执行这些操作）。第一个需要额外的O(lg n)步骤，第二个需要额外的空间。但我不确定是否有更好的选择。

- James Kanze

---

B 的顺序很重要，你不能对其进行排序。而且，即使它按升序或降序排列，你仍需要将右侧的元素（即具有更高索引的元素）向左移动以填补删除的元素位置。 - SubmittedDenied

每当您从std::vector中删除元素时（除非是最后一个），都必须移动其他元素。但是像std::remove_if这样的函数实际上并不会删除元素；一旦它们将要保留的元素移动到开头，您就可以在末尾删除一块元素。从后面开始的原因是您不会使未处理的索引无效。如果您无法对B进行排序，则唯一的解决方案是使用位向量；之后，您可以使用std::remove_if和erase或copy_if。 - James Kanze

Answer 4

无标记，O(n) 时间，但也需要 O(n) 空间，在伪代码中：

// create a boolean array indicating which elements are to be deleted
D = new boolean[N]
fill(D, false)
for (b in B) {
  D[b] = true
}

// compact `A in place
src = 0
dest = 0
while (src < N) {
  if (!D[src]) {
    A[dest++] = A[src]
  }
  src++
}

new_N = dest

- NPE

Answer 5

如果你可以假设 b 已经排序，那么在迭代时你可以进行移位操作（如果没有排序，你可以使用 O(n*log(n)) 的时间对 b 进行排序）。

int[] b;
int[] a;
int first=0,bInd=0;
for(int i = 0;i<a.length;i++){
    if(bInd>=b.length || b[bInd]!=i){
        a[first]=a[i];
        first++;
    }else{
        bInd++;
    }
}

- ratchet freak

---

当你移动A时，A中项目的位置会发生变化，因此你无法对B进行排序。B可能是[0, 0]，这意味着你需要删除A中的前两个元素。 - SubmittedDenied

@submitted 我在这里假设B中的元素是数组A 在任何删除之前的确切索引，因此b=[0,0]将无效或意味着只有第一个应该被删除。 - ratchet freak

@submittedDenied，排序不会影响真正的解决方案。B中的索引是相对于初始数组的。移位不会对数组B产生任何影响。 - learner

排序将允许您按照从后往前的顺序进行删除。因此，删除不会影响任何尚未删除对象的索引。 - James Kanze