4

我想编写一个需要 2 个数组的函数——
一个数组是源数组，另一个数组是索引数组。
我想从第二个数组中删除源数组索引处的所有元素。
假设第一个数组是：{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) 中完成？

4

6 回答 6

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

如果可以使用墓碑值，例如，如果保证 -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]; 
}

arr 输入长度：n arr 新长度：i

于 2013-07-14T12:11:30.700 回答
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;
}
于 2013-07-14T12:23:54.967 回答
1

可能你想要这样的东西：

#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;
}
于 2013-07-14T12:25:28.193 回答
0

伪代码

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

于 2013-07-14T12:16:20.503 回答
0

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

于 2013-07-14T12:17:09.670 回答
0

这是一个就地完成的解决方案，不在堆上分配内存，不需要标志值，并且在 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 兼容性来实现 VLA。

于 2013-07-14T14:17:38.983 回答