欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数组“去重”与“排序”

程序员文章站 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);
}