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)

Do you know the maximum and minimum of your values in the dynamically allocated array? — Jayantha Lal Sirisena
– Jayantha Lal Sirisena, Commented Feb 7, 2012 at 13:54
@Patryk: I guess that Jayantha's question is whether the values are fixed and small (by some definition of small)... probably the intent is that you could create an array of N bool (or use a bitmap), walk over the array O(N) marking the elements that are present. Then the bitmap will contain the set of values that are present in the original array. — David Rodríguez - dribeas
– David Rodríguez - dribeas, Commented Feb 7, 2012 at 14:35

Community · Accepted Answer · 2017-05-23 12:15:07Z

5

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.

edited May 23, 2017 at 12:15

CommunityBot

11 silver badge

answered Feb 7, 2012 at 13:53

Jacob

34.7k15 gold badges116 silver badges168 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

Luchian Grigore · Accepted Answer · 2012-02-07 13:53:58Z

2

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

answered Feb 7, 2012 at 13:53

Luchian Grigore

260k68 gold badges465 silver badges634 bronze badges

Comments

Some programmer dude · Accepted Answer · 2012-02-07 14:07:10Z

1

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.

edited Feb 7, 2012 at 14:07

answered Feb 7, 2012 at 13:54

Some programmer dude

411k36 gold badges420 silver badges655 bronze badges

Comments

Archit · Accepted Answer · 2015-05-15 17:38:12Z

#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.

Baptiste Wicht · Accepted Answer · 2012-02-07 13:53:55Z

0

You can use an hash set (unordered_set) to store each value of the source array. The set will automatically store only unique values. Then, if you really need an array and not a set, you can create an array of the good size and fill it with the elements of the set.

answered Feb 7, 2012 at 13:53

Baptiste Wicht

7,7338 gold badges52 silver badges116 bronze badges

Comments

Jayantha Lal Sirisena · Accepted Answer · 2012-02-07 13:58:26Z

0

If you know the maximum and minimum you can create a new array with all the possible values you can get and then loop through your dynamic array . For each value set 1 for the new array by taking as the index of the value. As an example:- say you have data like this 1,2,2,4,6

if the range is 1 to 7

the second array will be like this

1 2 3 4 5 6 7
1 1 0 1 0 1 0

The complexity of the algo will be 2n

answered Feb 7, 2012 at 13:58

Jayantha Lal Sirisena

21.4k11 gold badges74 silver badges94 bronze badges

Collectives™ on Stack Overflow

How to efficiently extract unique values from array?

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

Comments

Comments

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related