如何删除第一个数组中某些索引位置的所有元素，并且这些索引位置是从第二个数组中获取的？

Question

我想写一个函数，它接受两个数组作为参数-
一个数组是源数组，另一个数组是索引数组。
我想从第二个数组中获取索引，并删除源数组中这些索引所对应的元素。
例如，第一个数组是：{12,5,10,7,4,1,9}，索引数组是：{2,3,5}。
那么第一个数组中索引为2、3、5的元素，即10、7和1将被删除。
因此，第一个数组变为：{12,5,4,9}。
如果索引数组已排序，则我的O(N)解决方案如下：

#include<iostream>
using namespace std;
int main()
{
    int arr[]={12,5,10,7,4,1,9},n=7,indices[]={2,3,5},m=3;
    int j=0,k=0;
    for(int i=0;i<n,k<m;i++)
    {
        if(i!=indices[k])
            arr[j++]=arr[i];
        else
            k++;
    }
    for(i=0; i<j; i++)
        cout<<arr[i]<<" ";
    return 0;
}

如果索引数组未排序，如何以O(n)的时间复杂度解决呢？

- Shekhar Kumar

---

将结果存储在新数组中，可以吗？也就是说，不是原地操作。 - lulyon

@Alex 首先对索引进行排序，复杂度将为 O(n+m*lgm)。O(n+m*lgm) < O(n+m*n) = O(n*m) - johnchen902

@shek8034 有没有任何一个值在 arr 中永远不会出现，但是可以由 int 表示？ - johnchen902

@johnchen：你可以将其视为int max。 如果您有解决方案，请提供答案。 - Shekhar Kumar

如果你想要 O(n) 的时间复杂度，那么只需要使用非比较的 O(n) 排序算法对索引进行排序即可。 - JoeG

FYI，for(int i=0; i<n, k<m; i++) 等同于 for(int i=0; k<m; i++)。 - Elliott

Answer 1

• 循环遍历过滤器数组，并使用墓碑标记死元素
• 创建一个新的数组，逐步复制并跳过墓碑元素

如果可能，请使用墓碑值。例如，如果保证输入中不会出现-1，则-1可以成为墓碑值。如果不可能，请使用布尔标记数组，并将其初始化为false。

标记后的原地过滤：

for(int i=0,j=0;j<n;i++,j++){
  if( a[j] == TOMBSTONE ){
     i--; // the loop will add +1
     continue;
  }
  if(i==j)
    continue; // skip, no need to write
  arr[i]=arr[j]; 
}

输入数组长度：n 新数组长度：i

（注：本文涉及IT技术，不提供解释）

- Zoltán Haindrich

---

你能原地操作吗？ - Shekhar Kumar

Answer 2

根据评论：

“在arr中永远不会出现但可以用int表示的值”是否存在？

您可以将其视为“int max”。

现在您可以使用removeIndices。

#include<iostream>
#include<limits>

int removeIndices(int* arr, int n, int* indices, int m){
    const int NEVER_IN_ARRAY = std::numeric_limits<int>::max();
    for(int i = 0; i < m; i++)
        arr[indices[i]] = NEVER_IN_ARRAY;
    for(int from = 0, to = 0; from < n; from++)
        if(arr[from] != NEVER_IN_ARRAY)
            arr[to++] = arr[from];
    return n - m;
}
int main(){
    int arr[] = {12, 5, 10, 7, 4, 1, 9}, n = 7, indices[] = {2, 3, 5}, m = 3;
    int newSize = removeIndices(arr, n, indices, m);
    for(int i = 0; i < newSize; i++)
        std::cout << arr[i] << " ";
    return 0;
}

---

编辑：随着

#include<algorithm>
#include<functional>

我们可以做到以下几点：

int removeIndices(int* arr, int n, int* indices, int m){
    const int NEVER_IN_ARRAY = std::numeric_limits<int>::max();
    std::for_each(indices, indices + m, [arr](int index){ arr[index] = NEVER_IN_ARRAY; });
    int* p = std::remove_if(arr, arr + n, std::bind2nd(std::equal_to<int>(), NEVER_IN_ARRAY));
    return p - arr;
}

- johnchen902

---

您可以创建一个布尔型的墓碑向量，并保持同步，从而摆脱需要标志值的需要：如果原始数组的大小已知，则这的成本是适度的；如果未知，则需要进行堆分配。使用 std::remove_if 可以几乎肯定地加快删除索引的速度。 - Yakk - Adam Nevraumont

@Yakk 使用 remove_if 进行批准。但是对于一个布尔向量，OP想要在原地完成，因此... - johnchen902

现在indices中的重复项已经被删除。设置int num_left = std::remove_if(...)-arr;，并返回该值--更加安全。(使用remove_if的一个优点是--你可以在顶部代码中使用to来复制它) - Yakk - Adam Nevraumont

Answer 3

也许您想要类似这样的东西：

#include<iostream>
#define INVALID 99999  //to mark the elements who will disappear
using namespace std;


int main()
{
    int arr[] = {0,1,2,3,4,5,6,7,8,9,10};
    int indices = {3,1,5};

    int indices_len = 3;
    int arr_len = 3;

    for(int i=0; i<indices_len; i++){
        arr[indices[i]] = INVALID;
    }

    int invalid_count=0;
    for(int i=0; i<arr_len; i++){
        if(arr[i] == INVALID){
            invalid_count++;
        }

        arr[i-invalid_count] = arr[i];
    }
    return 0;
}

- taufique

Answer 4

伪代码

int old_arr[MAX_SIZE], new_arr[MAX_SIZE];
bool to_del[MAX_SIZE] = {0};
int index_to_del[MAX_SIZE];

for (size_t i = 0; i < MAX_SIZE; ++i) 
    to_del[index_to_del[i]] = true;

size_t new_size = 0; 
for (size_t i = 0; i < MAX_SIZE; ++i) 
    if (!to_del[i])
        new_arr[new_size++] = old_arr[i];

编辑 上面的代码片段占用了额外的空间。 如果我们必须在原地进行操作，那么每次删除一个元素时，我们都必须将所有连续的元素向左移动1个位置。在最坏的情况下，这可能是O(n ** 2)。如果您想在不复制数组元素的情况下进行原地操作，则可以使用vector。

如果删除操作超过读取操作，请考虑使用multiset

- bsd

---

建议一种不使用额外空间的方法来完成它。 - Shekhar Kumar

Answer 5

这里有一个解决方案，它可以原地完成操作，不会在堆上分配内存，也不需要标志值，并且可以在O(N+M)的时间内完成：

#include <cstddef>

template<std::size_t N>
std::size_t removeIndices( int(&src)[N], std::size_t srcSize, int const* removal, std::size_t removeSize )
{
  bool remove_flags[N] = {false};
  for( int const* it = removal; it != removal+removeSize; ++it ) {
    remove_flags[*it] = true;
  }
  int numberKept = 0;
  for( int i = 0; i < srcSize; ++i ) {
    if( !remove_flags[i] ) {
      if (numberKept != i)
        src[numberKept] = src[i];
      ++numberKept;
    }
  }
  return numberKept;
}

请注意，它需要完全访问源数组，因为我创建了一个相同大小的临时堆栈缓冲区bool。在C++1y中，您将能够使用可变长度数组或类似类型而无需编译时知识来执行此操作。

请注意，一些编译器已经通过（希望部分）C99兼容性实现了VLAs。

- Yakk - Adam Nevraumont

Answer 6

你必须将结果添加到一个新的数组中。只需遍历所有元素，如果索引在要删除的数组中，则继续，否则将其复制到新数组中。你可以查看MFC的CArray类，它有RemoveAt方法。

- ahmedsafan86