0

I want to write a C program that removes repeated values in an array and keep only the last occurrence.

For example I have to arrays:

char vals[6]={'a','b','c','a','f','b'};
int pos[6]={1,2,3,4,5,6};

I want to write a function so that the elements in the array after would be:

char vals[4]={'c','a','f','b'};
int pos[4]={3,4,5,6};

I know how to delete elements in general but in this case I am looking for a way where I could also delete the values in the pos array (associated with the Vals array)

  • Does this answer your question? [Algorithm: efficient way to remove duplicate integers from an array](https://stackoverflow.com/questions/1532819/algorithm-efficient-way-to-remove-duplicate-integers-from-an-array) – fdermishin Dec 13 '20 at 01:27
  • Well sort of.I am looking to delete every occurrence of the repeated values except the last one, so that is opposite of what I am looking for. –  Dec 13 '20 at 01:28
  • I would say the best is to find duplicate entries online first and overwrite them, like a hash map, but of course this may not be possible or desirable in certian cases. – Neil Dec 13 '20 at 05:56

1 Answers1

0

Overwriting duplicate elements, per se, isn't particularly complicated. But right here you have the additional constraint of wanting the last index of each element you find. This can be solved easily when you search for duplicates:

unsigned remove_duplicates (char * restrict array,
                            unsigned * restrict positions, unsigned count) {
  // assume positions is uninitialized
  unsigned current, insert = 0;
  for (current = 0; current < count; current ++) {
    // first, see if the value is already in the array
    unsigned search;
    for (search = 0; search < current; search ++)
      if (array[current] == array[search]) break;
    if (search < current)
      // if we found it, we just have a new position for it
      positions[search] = current + 1; // +1 because your positions are 1-based
    else {
      // otherwise, write it into the array and store its position
      // insert tracks the insertion pointer (i.e., the new end of the array)
      array[insert] = array[current];
      positions[insert] = current + 1;
      insert ++;
    }
  }
  // at this point we're done; insert will have tracked the number of 
  // unique elements, which we can return as the new array size
  // the positions won't be sorted; you can sort both arrays if you want
  return insert;
}
aaaaaa123456789
  • 5,541
  • 1
  • 20
  • 33
  • Thank you for this.I have some questions though.What is insert in this case? –  Dec 13 '20 at 01:45
  • 1
    @compscigirl Since the deduplication is being done in place (i.e., using the same array), you have to somehow make sure that you add the new deduplicated elements at the right positions. If the last element you inserted was at position 3, the next unique element should be at position 4, no matter how many duplicates you find between them. The `insert` variable will track that insertion position, so that the unique elements can be (re)inserted correctly into the array, at consecutive positions. Its final value will also be the new size of the array — which is why I return that to the caller. – aaaaaa123456789 Dec 13 '20 at 01:47