数组“去重”与“排序”
程序员文章站
2024-03-22 19:52:22
...
“去重”与“排序”
- 输入有2行,第1行为一个正整数,表示需要输入n个数。(n<=100且输入的数不大于1000)。第2行有n个用空格隔开的正整数。
- 输出也是两行,第1行为一个正整数j,表示去重后剩余有j个数。第2行为j个用空格隔开的正整数,为上述输入数去重后从小到大已排好序的这样一个序列。
样例输入
10
20 40 32 67 40 20 89 300 400 15
样例输出
8
15 20 32 40 67 89 400
用到了三种解决方法:
1.桶排序:先去重后排序
2.快速排序:先排序后去重
3.C++ STL库中的sort和unique函数:直接排序和去重。
#include <iostream>
#include <algorithm>
using namespace std;
int a[1001];
void bucket_sort(int n) //桶排序:去重+排序
{
int i,j=0,t;
for(i=1;i<=1000;i++)
{
a[i]=0;
}
for(i=1;i<=n;i++)
{
cin >> t;
a[t]++;
}
for(i=1;i<=1000;i++)
{
if(a[i]!=0)
j++;
}
cout << j << endl;
for(i=1;i<=1000;i++)
{
if(a[i]!=0)
cout << i << ' ';
}
}
void quick_sort(int l,int r)//快速排序
{
if(l<r)
{
int i=l,j=r;
int x=a[i];
while(i<j)
{
while(i<j&&a[j]>x)
j--;
if(i<j)
a[i++]=a[j];
while(i<j&&a[i]<x)
i++;
if(i<j)
a[j--]=a[i];
}
a[i]=x;
quick_sort(l,i-1);
quick_sort(i+1,r);
}
}
void quick_sort1(int n)//快速排序:排序+去重
{
int i,j=1;
for(i=1; i<=n; i++)
{
cin >> a[i];
}
quick_sort(1,n);
for(i=2; i<=n; i++)
{
if(a[i]!=a[i-1])
j++;
}
cout << j << endl;
cout << a[1] << ' ';
for(i=2; i<=n; i++)
{
if(a[i]!=a[i-1])
cout << a[i] << ' ';
}
}
void sort_unique(int n)//直接排序+去重
{
int i,p;
for(i=1;i<=n;i++)
{
cin>>a[i];
}
sort(a+1,a+n+1);
p=unique(a+1,a+n+1)-a-1;
cout<<p<<endl;
for(i=1;i<=p;i++)
{
cout<<a[i]<<' ';
}
}
int main()
{
int n;
cin >> n;
//bucket_sort(n);
//quick_sort1(n);
sort_unique(n);
}