How to remove the whole element that is in some index of the first array, and the index is taken from the second array?

Question

I want to write a function that takes 2 arrays -
One array is the original array, and the other array is an array of indices.
I want to remove all those elements that are present in the indices of the original array taking indexes from the second array.
Suppose the first array is {12,5,10,7,4,1,9} and the index array is {2,3,5}.
Then the elements with an index of 2,3,5. i.e. 10, 7 and 1 are removed from the first array.
So, the first array becomes: {12,5,4,9}.
If the index array is sorted, then my solution is 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; } 

How to do this in O (n) if the array of indices is not sorted?

Answer 1

According to the comments:

Is there any value that will never be displayed in arr , but int can be represented?

You can accept this as an int max .

Now you can use 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; } 

---

Edit: Using

 #include<algorithm> #include<functional> 

We can do it:

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

Answer 2

• cycle through the filter and mark the dead elements with tombstones
• create a new array and copy step by step, skipping the tombstones

if you can use the value of the headstone, for example, if it is guaranteed that -1 does not appear in the input, then -1 can be the value of the headstone; if this is not possible, use an array of logical markers, run them in false

filtering the place after marking:

 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 input length: n arr new length: i

Answer 3

Maybe you want something like this:

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

Answer 4

pseudo code

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

Edit The above snippet consumes additional space. If we had to do this in place, then each time we delete an element that we will have to shift all consecutive elements by 1. In the worst case, it can be O (n ** 2). If you want to do this in place without copying the elements of the array, you can use vector .

If you delete the number of excesses, then use multiset

Answer 5

You must add the result to the new array 1 - just iterate over all the elements, if the index is in the delete array continue else, copy it to the new array, you can look at the CArray class from MFC, which has a RemoveAt method

Answer 6

Here is a solution that does this in place, does not allocate memory on the heap, does not require flag values, and does it in O (N + M) time:

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

Note that he needs full access to the original array, because I am creating a temporary bool stack buffer that is the same size. In C ++ 1y, you can do this without knowing compilation time using variable-length arrays or similar types.

Note that some compilers implement VLA through (hopefully partial) C99 compatibility.