CODEWITHSUNDEEP
c++arrayssorting
Shekhar Kumar
Shekhar Kumar

Reputation: 2280

How to Delete all the element which are at some index of first array and the index is taken from second array?

I want to Write a function which takes 2 arrays-
One array is the source array and the other array is the array of indices.
I want to delete all those elements present at the indices of the source array taking the indices from the second array.
Suppose First array is : {12,5,10,7,4,1,9} and index array is : {2,3,5}.
Then the elements at index 2,3,5. i.e. 10, 7 and 1 are deleted from first array.
So first array becomes : {12,5,4,9}.
If the indices array is sorted,then my O(N) solution is:

#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 it in O(n) if the indices array is not sorted ?

Upvotes: 5

Views: 830

Answers (6)

johnchen902
johnchen902

Reputation: 9601

According to the comments:

Is there any value that will never appear in arr but is representable by int?

You can take that as 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: With

#include<algorithm>
#include<functional>

We can do:

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

Upvotes: 2

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275270

Here is a solution that does it 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 it needs full access to the source array, because I create a temporary stack buffer of bool that is the same size. In C++1y, you'll be able to do this without that compile time knowledge using variable length arrays or similar types.

Note that some compilers implement VLAs via (hopefully partial) C99 compatibility already.

Upvotes: 0

bsd
bsd

Reputation: 2717

PseudoCode

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 extra space. If we had to do it in-place, then every time, we delete an element we will have to shift all consecutive elements by 1. In worst case, this could be O(n**2). If you want to do it in-place without yourself copying array elements, you could use vector.

If deletes outnumber reads, then consider using multiset

Upvotes: 0

taufique
taufique

Reputation: 2751

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

Upvotes: 1

Zolt&#225;n Haindrich
Zolt&#225;n Haindrich

Reputation: 1808

  • loop thru filter array and mark dead elements with tombstones
  • create a new array, and copy step-by-step while skipping tombstones

if it's possible use a tombstone value, for example if it is guranteed that -1 doesn't appear in the input then -1 can be the tombstone value if this is not possible use an array of boolean markers, init them to false

in-place filtering 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

Upvotes: 2

ahmedsafan86
ahmedsafan86

Reputation: 1794

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

Upvotes: 0

Related Questions