题目分析

1. 输入的第一个数字N表示接下来一组要继续输入N个数字，这N+1个数字作为一组
2. 题目要求N个数字要进行去重并重新排序输出
3. 题目会给出若干组数字，对每一组数组都要像前面的处理，追加在上一轮的输出后面即可

方法一：普通sort排序

• 实现思路

  • 对于每一组的数字首先装进nums向量中，不去重

  • 直接对nums调用sort函数直接排序

  • 排序后作为一个有序递增数组，可以用双指针的方法进行去重，只输出不重复的部分

  • 最后对于每一组都这样处理即可

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

using namespace std;

int main() {
    int n;
    while(cin >> n) {                        // 输入个数N
        vector<int> nums;                    // 储存每一轮的所有生成的N个数字
        while(n) {                           // 处理输入和写入N个数字
            int a;
            cin >> a;
            nums.push_back(a);
            n--;
        }
        sort(nums.begin(), nums.end());      // 对该轮的数字进行排序，其中可能包含重复的数字
        
        for(int i = 0; i < nums.size();) {   // i指针标记一个位置
            int j = i + 1;                   // j指针开始从i指针后一个位置往后找
            for(; j < nums.size() && nums[i] == nums[j]; j++);    // 直到j指针找到下一个与i指针指向的数字不同的位置
            cout << nums[i] << endl;         // 输出所有i指针所指的数字，一定都是不重复的
            i = j;
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(nlogn)O(nlogn)$，其中开销最大的部分就是排序sort函数部分，代价为$O(nlogn)O(nlogn)$
• 空间复杂度：$O(n)O(n)$，需要借助辅助nums数组装载所有的数字

方法二：桶排序

• 实现思路

  • 由于题目规定随机生成的数字范围在[1,1000]中，对于这种类型有限的排序可以考虑桶排序的方案

  • 我们只要准备一个1001长度的容器，进行对每一个数字出现标记工作即可

  • 然后按照索引顺序和标记顺序可以实现排序工作

  • 并且标记也可以帮我们实现去重工作

  • 最后输出排序结果即可

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n;

    while(cin >> n) {                        // 输入个数N
        int a[501] = {0};                   // 直接用一个1001大小的数组存储出现的数字
        while(n) {                           // 对N个数字进行处理
            int num;
            cin >> num;                      // 分别输入这一轮的N个数字
            a[num] = 1;                      // 对出现的数字标记为1
            n--;
        }
        for(int i = 0; i < 501; i++) {
            if(a[i] == 1) cout << i <<endl;  // 每一轮根据桶排序的原理进行按序输出
        }
    }
    return 0;
}

复杂度分析

• 时间复杂度：$O(n+val)O(n+val)$，遍历所有的数字一轮的时间代价加上遍历我们的桶排序空间的时间代价
• 空间复杂度：$O(val)O(val)$，由于数据的范围为$1\le val\le 5001\backslash le\; val\; \backslash le\; 500$，因此空间代价为$O(val)O(val)$