6.4 数组去重

“数组去重是一个很实用的技巧，”我说道，”就像整理书架时，我们要把重复的书只留一本一样。”

6.4.1 去除重复数字（按序输出）

题目描述： 给你 N 个数（N≤100），每个数都在（0∼1000）之间，其中由很多重复的数字，请将重复的数字只保留一个，并将剩下的数由小到大排序并输出。

输入格式： 输入有 2 行；第 1 行为 1 个正整数，表示数的个数：N；第 2 行有 N 个用空格隔开的整数。

输出格式： 第 1 行为 1 个正整数 M，表示不相同数的个数。接下来的 M 行，每行一个整数，表示从小到大排好序的不相同的数。

样例输入：

10
20 40 32 67 40 20 89 300 400 15

样例输出：

8
15
20
32
40
67
89
300
400

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int cnt[1010] = {0};  // 统计数组初始化为0
    int n, x;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> x;
        cnt[x]++;  // 统计每个数出现的次数
    }
    
    int unique_count = 0;  // 不相同数的个数
    for(int i = 0; i <= 1000; i++){
        if(cnt[i]) unique_count++;  // 统计不同数字的个数
    }
    
    cout << unique_count << endl;
    for(int i = 0; i <= 1000; i++){
        if(cnt[i])  // 只输出出现过的数字
            cout << i << endl;
    }
    return 0;
}

算法解析：

1. 统计每个数字出现的次数
2. 遍历统计数组，统计有多少个不同的数字
3. 按顺序输出所有出现过的数字，自然实现去重和排序

6.4.2 去除重复数字（保持原顺序）

题目描述： 给你 N 个数（N≤100），每个数都在（0∼1000）之间，其中由很多重复的数字，请将重复的数字只保留一个，输出时不要改变原来数字的相对位置。

输入格式： 输入有 2 行；第 1 行为 1 个正整数，表示数的个数：N；第 2 行有 N 个用空格隔开的整数。

输出格式： 第 1 行为 1 个正整数 M，表示不相同数的个数。接下来的 M 行，每行一个整数，为去重完的数字。

样例输入：

10
20 40 32 67 40 20 89 300 400 15

样例输出：

8
20
40
32
67
89
300
400
15

代码实现：

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a[110], cnt[1010] = {0}, n, unique_count = 0;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> a[i];      // 保存原数组
        cnt[a[i]]++;      // 统计出现次数
        if(cnt[a[i]] == 1) unique_count++;  // 第一次出现时计数
    }
    
    cout << unique_count << endl;
    for(int i = 1; i <= n; i++){
        if(cnt[a[i]]){          // 如果这个数还没有被输出过
            cout << a[i] << endl;
            cnt[a[i]] = 0;      // 标记为已输出，避免重复输出
        }
    }
    return 0;
}

算法解析：

1. 保存原数组，同时统计每个数字出现次数
2. 在输入时就统计不同数字的个数
3. 按原数组的顺序遍历，每个数字只输出第一次出现的位置
4. 使用标记避免重复输出