题意理解

得到一个数组,将其中重复出现过的数字只保留一个,然后将剩余的数字从小到大排序。

方法一

读入的时候会有多组数据,我们用while()循环读入n,再读入数组中的n个数。

使用一个rp数据记录一个数是否出现过。如果出现过,就不加入数组num中去。最后使用sort()函数进行排序即可。

具体代码如下:

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int main()
{
    int n,x;
    vector<int> num;
    while(cin>>n)
    {
        num.clear();
        int rp[1001]={0};
        for (int i=0;i<n;i++)
        {
            cin>>x;
            if (!rp[x])
            {
                num.push_back(x);
                rp[x] = 1;
            }
        }
        sort(num.begin(), num.end());
        for (int i=0;i<num.size();i++) cout<<num[i]<<endl;
    }
    return 0;
}

时间复杂度:O(NlogN)O(NlogN)。在读入时遍历了一遍数组,排序的时间复杂度更高。
空间复杂度:O(val)O(val)。rp数组的长度固定,unordered_map中不超过val个数对。

方法二

使用unordered_map数据结构,把数组中出现过的数作为索引key,如果x出现了,则num[x]=1。这样无论数字x重复出现几次,x作为索引只有一个。同时,我们记录数组中的最大值maxm。最后,从1到maxm遍历,如果num的索引中包含i则输出,而且这样不需要排序。 alt

具体代码如下:

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

int main()
{
    int n,x;
    unordered_map<int, int> num;
    while(cin>>n)
    {
        num.clear();
        int maxm = 0;//记录一个最大值,作为输出时遍历的结尾。
        for (int i=0;i<n;i++)
        {
            cin>>x;
            num[x] = 1;//做一个标记。
            if (x > maxm) maxm = x;
        }
        for (int i=1;i<=maxm;i++)
        {
            //如果在num的索引中有i,则输出i。
            if (num.find(i)!=num.end())
            {
                cout<<i<<endl;
            }
        }
    }
    return 0;
}

时间复杂度:O(N)O(N)。在读入时遍历了一遍数组,没有排序过程。
空间复杂度:O(val)O(val)。unordered_map中不超过val个数对。