6.2 特殊统计问题

“有时候，我们需要解决一些特殊的统计问题，”我继续说道，”比如找出落单的筷子，或者找出缺失的数字。”

6.2.1 找筷子（找落单的数字）

题目描述： CX 小朋友找出了餐厅中所有的筷子，但遗憾的是这些筷子长短不一，而我们都知道筷子需要长度一样的才能组成双，更麻烦的是 CX 找出来的这些筷子数量为奇数，但是巧合的是，这些筷子中只有一只筷子是落单的，其余都成双，善良的你，可以帮 CX 找出这只落单的筷子的长度吗？

输入格式： 第一行读入一个数 N，它代表 CX 找到的筷子的根数。（10≤N≤10000）第二行是 N 个用空格隔开的数，代表筷子的长度。（筷子长度都是 1∼1000 之间的整数）

输出格式： 一行，落单的筷子的长度。

样例输入：

9
2 2 1 3 3 3 2 3 1

样例输出：

2

代码实现：

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

int main(){
    int cnt[1010] = {0};  // 统计数组初始化为0
    int n, x;
    cin >> n;
    
    while(n--){
        cin >> x;
        cnt[x]++;  // 统计每个长度出现的次数
    }
    
    int result;
    for(int i = 1; i <= 1000; i++){
        if(cnt[i] % 2 != 0){  // 找出现奇数次的数字
            result = i;
            break;
        }
    }
    cout << result;
    return 0;
}

算法解析：

1. 统计每个筷子长度出现的次数
2. 找出出现奇数次的长度，这就是落单的筷子
3. 由于题目保证只有一个落单的，找到第一个即可

6.2.2 缺失的数字

题目描述： 有 n 个数字，值就是 1 ~ n ，现发现丢失了 2 个数字，请你根据剩余的 n – 2 个数字，编程计算一下，缺失的是哪两个数字呢？

输入格式： 第 1 行为整数 N (N≤100000)。第 2 行有 N−2 个整数(均用空格隔开)表示了剩下 N−2 个数字的值。

输出格式： 一行，按数字从小到大顺序输出两缺失的数字。两个数字之间用一个空格隔开。

样例输入：

6 
4 3 1 5 

样例输出：

2 6

代码实现：

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

int cnt[1000005] = {0};  // 全局数组自动初始化为0

int main(){
    int n, x;
    cin >> n;
    
    for(int i = 1; i <= n-2; i++){
        cin >> x;
        cnt[x]++;  // 标记存在的数字
    }
    
    for(int i = 1; i <= n; i++){
        if(!cnt[i])  // 找未被标记的数字（缺失的数字）
            cout << i << " ";
    }
    return 0;
}

算法解析：

1. 用统计数组标记所有存在的数字
2. 遍历1到n，找出未被标记的数字
3. 这些未被标记的数字就是缺失的数字