How to efficiently extract unique values from array?

Question

I would like to extract unique values from my (dynamically allocated) array. I have something like this :

    [0]     0   int
    [1]     1   int
    [2]     2   int
    [3]     2   int
    [4]     2   int
    [5]     5   int
    [6]     6   int
    [7]     6   int
    [8]     8   int
    [9]     9   int
    [10]    10  int
    [11]    8   int
    [12]    12  int
    [13]    10  int
    [14]    14  int
    [15]    6   int
    [16]    2   int
    [17]    17  int
    [18]    10  int
    [19]    5   int
    [20]    5   int

I would like to have array of size 12 with every record in it being unique value form the other array.

How can I do that ?

EDIT I forgot to mention that I cannot use STL containers (like std::vector or std::list)

Answer 1

Use std::unique after sorting your array with your favorite sorting algorithm (e.g. std::sort)

Edit: Without STL, the simplest solution would be to find the min & max values in the array and dynamically allocate an array of bool. Traverse the array and if you see the element, set the corresponding bool element to true. Allocate a new int array with the total number of unique elements and fill it up with the data from the bool array.

Recommended: Sort the array and remove consecutive elements. Implementing quick sort isn't too hard, and if you're dealing with integers, radix sort might be better.

Answer 2

You can use a std::set. Add all the elements to it, at the end only unique values will be present.

Answer 3

First you need to sort the array, then iterate over the sorted array and check if the previous or next entry are the same as the current entry. If not then the value is unique.

Edit: I might have misunderstood the question... One way to get what you want is to iterate over the array. For each value check the value already exists in the other array, if not the copy it there. This might have to be done in two steps, once to get the number of unique entries (using an array of the same size as the existing) and one to get an array of correct size.

Answer 4

#include <iostream>
#include <stdlib.h>
using namespace std;

int cmpfun(const void * a, const void * b){
  return (*(int*)a - *(int*)b);
}
int main(){
  int n,i,j=0;
  cout<<"Enter the number of elements in the array:\n";
  cin>>n;
  int arr[n],arr_new[n];
  for(i=0;i<n;i++)
       cin>>arr[i];
  qsort(arr, n, sizeof(int), cmpfun); /*Sorting the array; if you aren't allowed to use any library sorting method,
                                   then I suggest to implement one sorting function on your own.*/

  for(i=0;i<n;i++){
       arr_new[j++]=arr[i];
        // Excluding all duplicates
       while(i<(n-1) && arr[i]==arr[i+1])
                 i++;
  }
  for(i=0;i<j;i++)
  cout<<arr_new[i]<<" ";

return 0;}

The main aim is to make sure duplicates are ignored. So, you should first sort the array and then in O(n) time, traverse the array, ignoring all repetitions. While traversing the array, copy all the unique values(values which you encounter for the first time) to the new array.

The only thing I find that can concern you is that the respective ordering of elements in the old array isn't preserved in the new array. But if you are only concerned with finding the unique values, then this method should work fine.