delete and shift array elements

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.

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()

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).

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.)

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.