Как эффективно извлечь уникальные значения из массива?

Question

Я хотел бы извлечь уникальные значения из моего (динамически распределяемого) массива.У меня есть что-то вроде этого:

    [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

Я хотел бы иметь массив размером 12, чтобы каждая запись в нем была уникальным значением из другого массива.

Как я могу это сделать?

РЕДАКТИРОВАТЬ Я забыл упомянуть, что не могу использовать контейнеры STL (например, std::vector или std::list)

Answer 1

Используйте std :: unique после сортировки массива с помощью вашего любимого алгоритма сортировки (например, std :: sort )

Редактировать: Без STL самым простым решением было бы найти минимальное и максимальное значения в массиве и динамически выделить массив bool.Пройдите по массиву и, если вы видите элемент, установите соответствующий элемент bool в true.Выделите новый массив int с общим количеством уникальных элементов и заполните его данными из массива bool.

Рекомендуется: Сортировать массив и удалить последовательные элементы.Реализация быстрой сортировки не слишком сложна, и если вы имеете дело с целыми числами, radix sort может быть лучше.

Answer 2

Вы можете использовать std::set. Добавьте все элементы к нему, в конце будут присутствовать только уникальные значения.

Answer 3

#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) пройти через массив, игнорируя все повторы.Обходя массив, скопируйте все уникальные значения (значения, с которыми вы сталкиваетесь в первый раз) в новый массив.

Единственное, что меня беспокоит, так это то, что соответствующий порядок элементов в староммассив не сохраняется в новом массиве.Но если вас интересует только поиск уникальных значений, тогда этот метод должен работать нормально.

Answer 4

Сначала необходимо отсортировать массив, затем выполнить итерацию по отсортированному массиву и проверить, совпадают ли предыдущая или следующая запись с текущей записью.Если нет, то значение является уникальным.

Редактировать: Возможно, я неправильно понял вопрос ... Один из способов получить то, что вы хотите, - это перебрать массив.Для каждого значения проверьте, что значение уже существует в другом массиве, если нет, скопируйте его туда.Это может быть сделано в два этапа: один раз, чтобы получить число уникальных записей (используя массив того же размера, что и существующий), и один, чтобы получить массив правильного размера.

Answer 5

Если вы знаете максимум и минимум, вы можете создать новый массив со всеми возможными значениями, которые вы можете получить, а затем перебрать свой динамический массив. Для каждого значения установите 1 для нового массива, взяв в качестве индекса значение. В качестве примера:- скажем, у вас есть такие данные 1,2,2,4,6

, если диапазон от 1 до 7

второй массив будет таким

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

Сложность алгоритма будет 2n

Answer 6

Вы можете использовать хэш-набор (unordered_set) для хранения каждого значения исходного массива. Набор будет автоматически хранить только уникальные значения. Затем, если вам действительно нужен массив, а не набор, вы можете создать массив хорошего размера и заполнить его элементами набора.