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

Question

我想编写一个需要 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) 内做到这一点？

Answer 1

根据评论：

是否存在永远不会出现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;
}