Блог

Главная - Вопросы по программированию - Учитывая несортированный массив, как удалить дубликаты, а затем отсортировать его?

Учитывая несортированный массив, как удалить дубликаты, а затем отсортировать его?

#c #arrays #c

#c #массивы #c

Вопрос:

У меня возникают проблемы с этим, вы можете мне помочь?

Я успешно удаляю дубликат, но затем я использую пузырьковую сортировку для его сортировки, но это неэффективно.

Как я могу удалить дубликат, а затем отсортировать его? Использование 2 функций не может принести то, что я хочу.

 #include <stdio.h>
#include <conio.h>

int arr[100];
int n;
void RemoveDuplicate(int arr[]);
void Print(int arr[]);

int main()  
{
    int i;
    printf("Enter n:");
    scanf("%d",amp;n);
    for(i=0;i<n;i  )
        scanf("%d",amp;arr[i]);
    RemoveDuplicate(arr);
    Print(arr);
    getch();    
    return 0;
}

void Print(int arr[])
{
    int i;
    for(i=0;i<n;i  )
        printf("%d ",arr[i]);
}

void RemoveDuplicate(int arr[])
{
    int i,j,k;
   for(i=0;i<n;i  )
    {
    for(j=i 1;j<n;)
        {
        if(arr[i]==arr[j])
            {
            for(k=j;k<n;k  )
                {
                arr[k]=arr[k 1];
                }
            n--;
            }
        else
            j  ;
        }
    }   
}

Комментарии:

1. Переверните операции. Отсортируйте, затем удалите дубликаты. Делает это намного проще.

2. Подсказка: обычно это делается в противоположном направлении: сначала сортируется последовательность, а затем удаляются дубликаты. Удаление дубликатов в несортированной последовательности — это боль.

3. C или C ? Пожалуйста, выберите один.

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

5. В C вы можете использовать std::set контейнер для хранения уникальных элементов

Ответ №1:

Все примеры не проверены и начинаются со следующего

 if (n<1 || n > sizeof(arr))
  return;

auto begin = std::begin(arr);
auto end = begin n;

Использование std::set

 std::set<int> unique(begin, end);
std::copy(unique.begin(), unique.end(), std::begin(arr));
int size = unique.size();

Использование кучи

 std::make_heap(begin, end);
std::sort_heap(begin, end);
auto last = std::unique(begin, end);
auto size = std::distance(begin, last);

Просто используя std::sort вместо sort_heap

 std::sort(begin, end);
auto last = std::unique(begin, end);
auto size = std::distance(begin, last);

Использование кучи с ручным pop

 std::make_heap(std::begin(arr), std::end(arr));
auto first = begin;
auto last = end;
auto sorted = std::prev(last);
std::pop_heap(first, last--);  // initial value
while (first != last)
  std::pop_heap(first, last--);
  if (*last != *sorted amp;amp; last != sorted)
    *--sorted = *last;
}
auto size = std::distance(sorted, end);
std::copy(sorted, end, begin); // move values to start of array

Условие

 last != sorted

будет иметь значение false до первого дубликата и true после этого, поэтому цикл можно разделить на две части для возможного повышения производительности, но предсказатель ветвления должен устранить большинство проблем с производительностью из-за этого.

Если количество уникальных значений невелико и имеет небольшой разброс, а ‘n’ велико, используйте подсчетный массив.

Пример подсчета символов для std::векторный текст;

 std::array<int,256> count;
std::vector<char> resu<
for (auto ch : text)
  count[ch]  ;
for (auto idx = 0; idx < count.size();   idx)
  if (count[idx]) 
    result.emplace_back(idx);

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

 std::unordered:set<int> unique(begin, end);
std::copy(unique.begin(), unique.end(), std::begin(arr));
int size = unique.size();
std::sort(begin, begin size);