Geek Answers Handbook

How to efficiently extract unique values ​​from an array?

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 an array of size 12, with each entry in it being a unique value from another array.

How can i do this?

EDIT I forgot to mention that I cannot use STL containers (e.g., std::vectoror std::list)

+5
source share
6 answers

First you need to sort the array, then iterate over the sorted array and check if the previous or next records match the current record. If not, the value is unique.

: , ... , , - . , , . , , ( , ), , .

+1

std:: unique (, std:: sort)

Edit: STL bool. , , bool true. int bool.

: . , , .

+5

std::set. , .

+2
#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;}

, , . , , O (n) , , . (, ) .

, , , . , .

+1

- (unordered_set) . . , , , .

0

, , , . , 1 , . :- , 1,2,2,4,6

1 7

,

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

2n

0

More articles:


All Articles