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

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

[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 с каждой записью в это время уникального значения формирования другого массива.

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

EDIT Я забыл упомянуть, что я не могу использовать STL контейнеры (например, std::vector или std::list)

источник

2012-02-07 Patryk

Знаете ли вы максимальные и минимальные значения ваших значений в динамически распределенном массиве? –

@Jayantha Я могу получить это значение да. Но зачем? – Patryk

@Patryk: Можете ли вы использовать алгоритмы STL? – Jacob

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

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

источник

2012-02-07 13:54:01

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

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

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

источник

2012-02-07 13:53:27 Jacob

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

источник

2012-02-07 13:53:55

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

источник

2012-02-07 13:53:58

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

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

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

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

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

источник

2012-02-07 13:58:26

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

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

источник

2015-05-15 17:38:12

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

ответ

Смежные вопросы