解题思路:
这个输入需要一些技巧,首先,他给的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;
}


点赞(0)
 

0.0分

0 人评分

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程,并配有习题和答疑,点击了解:

一点编程也不会写的:零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码?手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的 必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程:算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表 共有 1 条评论

dotcpp0751747 9月前 回复TA
似乎sort里面,输入有0时,会出现bug