时间戳

首页 > 解决方案 > 给定一个未排序的数组，如何删除重复项然后对其进行排序？

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",&n);
    for(i=0;i<n;i++)
        scanf("%d",&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++;
        }
    }   
}

标签： c++arraysc

解决方案

所有示例均未经测试，并以以下内容开头

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);

将堆与手动弹出一起使用

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 && last != sorted)
    *--sorted = *last;
}
auto size = std::distance(sorted, end);
std::copy(sorted, end, begin); // move values to start of array

条件

last != sorted

在第一次重复之前为假，此后为真，因此可以将循环分成两部分以获得更好的性能，但分支预测器应该因此消除大多数性能问题。

如果唯一值的数量很小且分布范围很小，并且“n”很大，则使用计数数组。

std::vector 文本的字符计数示例；

std::array<int,256> count;
std::vector<char> result;
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);

推荐阅读