Function that would output all distinct values in an array

Question

I want to create a function that outputs the distinct values in a given array. For example, in the following sequence 2 2 1 1 5 2 , the distinct digits are 2 1 5. What I've done till now is:

void Distinct(int a[], int b[], int n){

    int i;                    //n is the number of elements for a and b
    int k=0;                  //a is the original array       
    int ac;


b[0] = a[0];
    for (i = 0; i <= n; ++i){
       if (a[i] != b[k])
                   {
                  k+=1; 
                  ac = a[i]; 
                  b[k] =ac; //b is where I want to put distinct digits
                      }

    }


    for ( i = 0; i < k; ++i)
    {
        printf("%d ", b[i]);
    }
}

But this is not enough, because what I've done is for the case when the numbers repeat one after another, I mean: 111122221 , I will get 121, and 1 at the end again.Can you please help me write a function that would consider this case, with repeating numbers scattered in the array ? Thank you.

Answer 1

There are many, many ways of doing this, and you haven't really specified whether you're after something that's simple to code or optimally performant or if you have an upper bound on the possible numbers or any other restriction that might help us tell which answer you need.

But your sample code implies you want the solution in a "low-level" language where we're dealing with arrays made up of bytes rather than some higher-level construct like a list/tuple/vector that makes it trivial to do things like remove elements from the middle. Therefore, I would suggest you run a sort algorithm on the input array (if you're in C++, that would be std::sort), then run your Distinct() function on that sorted array to create a correctly unique-ified array.

Answer 2

We have a name for a data structure that can only contain an element once: a set.

I have done this and tasks like it many times. Here is some pseudocode:

Array input = { ... };
Set output = ...;
for (int i : input) {
  output.add(i);
}
print output;

Initialize the array and a set that will contain the array's contents. Then iterate the array, adding each element to the set. If the set already contains an element with the same value, it will do nothing. Once this is done, print the set. It will contain each value stored in the array a maximum of once.