CODEWITHSUNDEEP
arraysalgorithmsortinglanguage-agnostic
Ege
Ege

Reputation: 941

delete and shift array elements

Suppose I have 2 sorted arrays. One of them has the elements to delete from the other. For example 

  int array1[]={1,2,3,4,5,6,7,8,9,10,11,12,13};
  int delete[]={5,9,12};

How should I delete the elements indicated in the delete array from array1 and shift the rest in array1 efficiently?

I don't want to go over all the elements of array1 since some of them will be unchanged. So I figured starting from 

  int j,i=0,n=0;
  for(j=delete[i+n];j<delete[i+1+n];j++){
      array1[i-n]=array1[i+1-n];
      n++;
  }

But I couldn't quite figure out how to do it right. Any ideas?

Upvotes: 0

Views: 3313

Answers (5)

Pham Trung
Pham Trung

Reputation: 11284

If you don't want to change the data structure, we can simply use two

binary search

to search for the lower bound and upper bound of the element you want to delete. For example array {1,1,2,2,3,3,3,4,5} and deleting element is 3 , so we have starting index and ending index is 4 and 6.

The next step is so simple, just collapse the segment specified by these two above indexes.

If you want to have faster performance, I suggest that you can use either binary search tree, or an array that store the frequency of elements.

Upvotes: 0

A. I. Breveleri
A. I. Breveleri

Reputation: 767

Assuming declarations like this:

var
   TgtArr : array of integer; // given- sorted array of elements to be modified
   TgtArrLen : integer;       // given- count of elements in TgtArr
   DelArr : array of integer; // given- sorted list of elements to be deleted
   DelArrLen : integer;       // given- count of elements in DelArr

And declaring these work variables:

var PutPtr, GetPtr, DelPtr : integer;  // local to deletion operation

This fragment will accomplish the deletion:

   DelPtr := 0;
   PutPtr := 0;
   for GetPtr := 0 to TgtArrLen-1 do begin
      if TgtArr[GetPtr]<>DelArr[DelPtr] then begin
         TgtArr[PutPtr] := TgtArr[GetPtr];
         PutPtr := PutPtr+1;
      end;
      if TgtArr[GetPtr]>=DelArr[DelPtr] then begin
         DelPtr := DelPtr+1;
         if DelPtr>=DelArrLen then break; // out of "for GetPtr" loop
      end;
   end;
   TgtArrLen := PutPtr;

(This is Delphi Pascal but you get the idea.)

Upvotes: 0

herohuyongtao
herohuyongtao

Reputation: 50667

This can be done in two-step scanning on the array1[] and delete[].

  1. Scan these two arrays at the same time and remember the positions in array1[] whose values also appear in delete[].

  2. Based on the positions you obtained in the first step, you should know, for each value in array1[], what positions should be after deleting values from delete[]. Then just copy to the right position. Done!

All the process can be done in O(n).

Upvotes: 0

Abhishek Bansal
Abhishek Bansal

Reputation: 12715

Deleting any element from an array is an O(N) operation. You can do the following.

  1. Initialize i = 0. count = 0.
  2. Iterate through array1[] and search for element delete[i].
  3. If you encounter an element array1[j] > delete[i], this means that delete[i] does not exist in array[]. Increment i to check for next element in delete array.
  4. If you find an element array1[j] == delete[i], then increment count. and increment i.

  5. Keep copying array1[j] to array1[j - count].

    array1[j - count] = array1[j];

  6. Continue till the end of array1. At the end, resize array1 to be of size size - count.

Upvotes: 1

Max
Max

Reputation: 1478

You did not specify a language. I would combine the arrays, make them a set and sort the result again. 

set combined_set = new Set(array1 + array2)
array = new Array(combined_set).sort()

Upvotes: 0

Related Questions