错误票据（c++，三种方法实现）

解题思路:
这个输入需要一些技巧，首先，他给的N表示输入多少行，然后每一行到底输入多少个数字我们不知道，这就需要我们去判断输入的结尾是不是换行号，这里提供了一个C++的判断方法：

cin.get()=='\n'

参考代码:

1、sort方法：建立一个数组，将输入的数据全部存在这个数组中，然后将整体数组进行排序，再对已经排好序的数组进行遍历，再找出断号和重号，复杂度为O(nlogn)

//【sort方法】
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, i, j=0;
    int lost, repeat; //lost：断号， repeat：重号
    int num[10000];
    cin >> n;
    while(n--) {
        while((cin >> num[j])) {
            //下面两句不能交换位置
            j++;
            if(cin.get() == '\n')
                break;
        }
    }
    sort(num, num+j);
    for(i=1; i<j; i++) {
        if(num[i]!=num[i-1]+1&&num[i]!=num[i-1]){
            lost=num[i]-1;
        }
        if(num[i] == num[i+1])
            repeat = num[i];
        if((lost!=0) && (repeat!=0))
            break;
    }
    cout << lost << " " << repeat;
    return 0;
}

2、哈希法：建立一个初值全部为0的数组（哈希数组），输入的数据作为数组的索引，将对应的值+1，遍历数组，值为0的就是断号，为2的就是重号，时间复杂度为O(n)，比sort排序快一些

//【hash】 使用hash可以避免使用sort排序
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    int lost=0, repeat=0; //lost：断号， repeat：重号
    int hash[10000]={0}, key; //hash表和键
    //ma：最大key值, mi：最小key值, 注意这里的最小key值一定要赋值，题目给出的是不大于10000的正整数
    int ma=0, mi=10000;
    cin >> n;
    while(n--) {
        while((cin >> key)) {
            hash[key]++;
            if(ma < key)
                ma = key;
            if(mi > key)
                mi = key;
            if(cin.get() == '\n')
                break;
        }
    }
    for(int i=mi+1; i<ma; i++) { //假设断号不可能发生在最大和最小号。
        if(hash[i] == 0) {
            lost = i;
        }
        if(hash[i] == 2) {
            repeat = i;
        }
        if((lost!=0) && (repeat!=0))
            break;
    }
    cout << lost << " " << repeat;
    return 0;
}

3、map方法：map也是键值对，且内部含有一棵红黑树，会按 键 升序排列（注意：本人没把最小值求出来！）

//【map】 --------- 最小值求不出来！！！！！大佬们请给出解题方法
#include <bits/stdc++.h>
using namespace std;
int main() {
    map<int, int> num;
    map<int, int>::iterator ite;
    int n, key;
    int lost=-1, repeat=-1;
    cin >> n;
    while(n--) {
        while(cin >> key) {
            num[key]++;
            if(cin.get() == '\n') {
                break;
            }
        }
    }
    for(ite=num.begin(); ite!=num.end(); ite++) {
        if(ite->second == 2) {
            repeat = ite->first;
        }
    }
    cout << lost << " " << repeat;
    return 0;
}