P4683 明明的随机数（入门）

解题思路

第一步，想清楚要做两件事。 明明要做的有两件事：去重——把重复的数字只保留一个；排序——把剩下的数字从小到大排好。一个聪明的办法是"先排序，再去重"，一步都不多算。

第二步，先排序。 sort(nums, nums + n) 从小到大排好。为什么先排序？因为排好序之后，相同的数字一定会紧紧挨在一起。比如输入的 10 个数是 20 40 32 67 40 20 89 30 42 15，排序后变成 15 20 20 30 32 40 40 42 67 89，可以看到两个 20 挨在一起，两个 40 挨在一起。

第三步，再去重。 从前往后扫一遍：第一个数肯定保留；后面的数如果和它前一个数不相等，就说明是一个新出现的数，保留下来；如果相等，就说明是重复的，跳过。把保留的数存进新数组 uniqueNums，计数器 uniqueCnt 加一。扫完，uniqueCnt 就是不相同的随机数个数，uniqueNums 里前 uniqueCnt 个数就是答案。

第四步，按格式输出。 第一行输出去重后的个数 uniqueCnt（也就是题目里的 M），第二行输出这 M 个数，用空格隔开。这两行缺一不可，很多同学容易忘记第一行，要特别留意。

记一个小技巧。 把"去重"放到"排序之后"做，是处理重复元素最常用的思路：排序后相同的元素必然相邻，扫描时只需要和上一个元素比较，就能判断当前元素是不是第一次出现，省去了每次都要回头查找的麻烦。

边界情况： N 最大 100，数组开 105 足够；如果所有数都相同，去重后只剩 1 个数；如果 N 个数全不同，去重后还是 N 个，输出格式不变。

参考代码

// P4683 明明的随机数：去掉重复的数字，再把剩下的数字从小到大排序输出
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    int nums[105];
    for (int i = 0; i < n; i++) cin >> nums[i];
    sort(nums, nums + n); // 先从小到大排序，相同的数会挨在一起
    int uniqueCnt = 0;
    int uniqueNums[105];
    for (int i = 0; i < n; i++) {
        if (i == 0 || nums[i] != nums[i - 1]) { // 和上一个不相同，就保留
            uniqueNums[uniqueCnt++] = nums[i];
        }
    }
    cout << uniqueCnt << endl;
    for (int i = 0; i < uniqueCnt; i++) {
        cout << uniqueNums[i];
        if (i < uniqueCnt - 1) cout << " ";
    }
    cout << endl;
    return 0;
}

复杂度分析

排序时间复杂度 O(N log N)，去重扫描是一趟 O(N) 的循环，所以总时间复杂度 O(N log N)。N 最大 100，完全没问题。用了两个长度 N 的数组 nums 和 uniqueNums，空间复杂度 O(N)。