I need to implement an algorithm to eliminate duplicates from an array (without creating a new one). I watched the implementation of the function std :: unique in pros.

int* unique(int* first, int* last) { if (first == last) return last; int* result = first; while (++first != last) { if (*result != *first) { *(++result) = *first; } } return ++result; }

Redid - removed templates. It seems that it even works, but I can not use it ... It is too inconvenient to use. I want to redo it into a normal version - at least with indices instead of this damn address arithmetic.

 typedef struct Array { int* data; int length; } Array; Array array_distinct(Array arr) { int index = 0; for (int i = 1; i < arr.length - 1; i++) { if (arr.data[index] != arr.data[i]) { arr.data[++index] = arr.data[i]; } } arr.length = index; return arr; } int main() { int input[] = { 1, 1, 2, 4, 5, 5, 6 }; Array a; a.data = input; a.length = sizeof(input) / sizeof(int); Array b = array_distinct(a); for (int i = 0; i < b.length; i++) { printf("%d\n", b.data[i]); } return 0; }

But something does not work out ... Help me please.

  • The data structure that you need is called an associative array . - 0andriy
  • @ 0andriy, Firstly, what side is associative arrays here? This is a set of key-value pairs. Where do you see me? Secondly, do you know many implementations of associative arrays on pure C? - PECHAPTER
  • This is most directly related, since the key is considered using a simple hash function, when you get an associative array, you immediately see duplicates, no additional gestures are needed. In general, programming is about data structures first of all, and then about functions (yes, except for functional PL) and code. - 0andriy
  • There are a lot of implementations, take a red-ebony and CRC32, for example. - 0andriy
  • What do you propose to use for the keys, and what kind of values? I do not really understand how this generally applies to my question. One way or another, I don’t have to - everyone decided below. - PECHAPTER

1 answer 1

Try this:

 Array array_distinct(Array arr) { for (int j = 0; j < arr.length - 1; ) { if (arr.data[j] == arr.data[j+1]) { for(int i = j+1; i < arr.length; ++i) arr.data[i-1] = arr.data[i]; arr.length--; } else ++j; } return arr; }

Written on the knee, but it seems to work ...

  • It seems to me that it is not particularly good to change the length of the loop within this cycle. - PECHAPTER
  • Why so? This is the current array length. Have you deleted an item? It is necessary to update the state of the array accordingly - specify its new length. - Harry
  • it seems to work ... - This algorithm will only work on an already sorted array. TS never said that it is. - Sergey
  • @Sergey Of course :) But he 1. gave the unique algorithm as the basis - did he really not read about the preconditions of his work? and 2. His sample data is sorted. Of course, these may be coincidences, but ... - Harry
  • Yes, I know that the array must be pre-sorted. - PECHAPTER