1
$\begingroup$

I am wondering if I can rearrange an array faster when I would like to delete more than one object.

You are given a List:

  • 1
  • 2
  • 2
  • 3
  • 4
  • 5
  • 7

And now you want to delete every "2" in the list. So what I would do, is:

int size = 7;
int array[size] = {1,2,2,3,4,5,7};
for(int i = size-1; i >= 0; i--){
   if(array[i] == 2){
      memcpy(&array[i],&array[i+1], size-i);
      size--;
   }
}

But this is not a efficent way doing so, is it? So I wonder if I could do this on a smarter way without allocating extra memory.

$\endgroup$
  • $\begingroup$ Firstly, find the first index, then the last, then call the memmove. $\endgroup$ – kelalaka Aug 6 at 20:26
  • $\begingroup$ So you presume a sorted list, what would you do for an unsorted list? $\endgroup$ – TVSuchty Aug 6 at 20:32
2
$\begingroup$

You can maintain a pointer that, in the $i$th iteration, points to the $i$th element that is not 2, i.e., the $i$th element in the final array. In each iteration, we only move the element to which the pointer points to the $i$th position.

int size = 7;
int array[7] = {1,2,2,3,4,5,7};
int i = -1;
int p = -1;
while (1)
{
    ++i;
    do ++p; while (p < size && array[p] == 2);
    if (p >= size) break;
    array[i] = array[p];
}
size = i;

In your example, it works as follows.

Initial: 1 2 2 3 4 5 7
After the 1st iteration: 1 2 2 3 4 5 7
                         i
                         p

After the 2nd iteration: 1 3 2 3 4 5 7
                           i   p

After the 3rd iteration: 1 3 4 3 4 5 7
                             i   p

After the 4th iteration: 1 3 4 5 4 5 7
                               i   p

After the 5th iteration: 1 3 4 5 7 5 7
                                 i   p

After the 6th iteration: 1 3 4 5 7 5 7
                                   i   p
$\endgroup$
  • $\begingroup$ I think the loop would be easier to understand if you iterated over p rather than i. $\endgroup$ – Gilles 'SO- stop being evil' Aug 7 at 7:01
  • $\begingroup$ Hey, what a smart algorithm! Did you come up with this on your own? $\endgroup$ – TVSuchty Aug 7 at 8:53
  • $\begingroup$ @TVSuchty Yes, but I think this algorithm is not hard and can be found in the Internet easily. $\endgroup$ – xskxzr Aug 7 at 8:57
  • $\begingroup$ For a (soon) first grader this is kinda mindblowing! I think this pointer concept can be used in various situations. $\endgroup$ – TVSuchty Aug 7 at 9:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.