编程论坛 → C++教室

无聊的话就做题吧，我从某版主那搜来的题，看着简单，做起来实在不简单

叶纤发布于 2020-02-26 13:18， 3824 次点击

常见水题，若有可能，会陆续补充
反正我没事就会写写
题目1：找出缺少的一个数（极易）
一个长度为 n 的整数数组，其中每个元素都大于等于0且小于等于n，且无重复，请找出“大于等于0且小于等于n”但不在此数组中的那一个数。
例如给出 { 5, 0, 2, 1, 4 }，则输出 3

题目2：找出缺少的两个数（中等）
一个长度为 n 的整数数组，其中每个元素都大于等于0且小于等于n+1，且无重复，请找出“大于等于0且小于等于n+1”但不在此数组中的那两个数。
例如给出 { 5, 0, 2, 1 }，则输出 3, 4

题目3：找出重复的一个数（极难）
一个长度为 n 的整数数组，其中每个元素都大于等于0且小于等于n-1，有一个数重复出现了两次或更多次，请找出此数。
例如给出 { 1, 0, 4, 3, 4, 4 }，则输出 4
原题：https://

题目4：找不重复出现的数（容易）
一个长度为 2*k+1 的整数数组，其中k个整数出现了2次，1个整数出现了1次，找出出现1次的那个整数。
例如给出 { 9, 5, 5, 9, 7, 1, 1 }，则输出 7

题目5：找重复两次的数（中等）
一个长度为 4*k+2 的整数数组，其中k个整数出现了4次，1个整数出现了2次，找出出现2次的那个整数。
例如给出 { 9, 5, 5, 9, 9, 5, 5, 9, 7, 1, 7, 1, 1, 1 }，则输出 7

31 回复

#2

叶纤2020-02-26 13:20

本帖只看代码

#3

纯蓝之刃2020-02-26 15:22

给这么高的分，你图啥

#4

return_02020-02-26 15:52

可以拿去买道具

#5

return_02020-02-26 15:59

rjsp搜来的吧
水题他最多

#6

return_02020-02-26 16:07

第一题答案：

程序代码：

#include<iostream>
using namespace std;
int main(){
    int n,s=0,d,u=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d;
        u+=d;
    }
    for(int i=0;i<=n;i++){
        s+=i;
    }
    cout<<s-u;
    return 0;
}

[此贴子已经被作者于2020-2-26 16:14编辑过]

#7

时光流逝2020-02-26 16:15

我刚开始觉得这题我还会做,可越敲代码越觉得不对劲

#8

return_02020-02-26 16:18

第二题答案：

程序代码：

#include<iostream>
using namespace std;
bool t[10010]={false};
int main(){
    int n,d;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d;
        t[d]=true;
    }
    for(int i=0;i<n+2;i++){
        if(t[i]==false)cout<<i<<" ";
    }
    return 0;
}

#9

叶纤2020-02-26 16:22

回复 6楼 return_0

大哥看题目，是数组

#10

return_02020-02-26 16:23

第三题答案：

程序代码：

#include<iostream>
using namespace std;
int t[10010]={0};
int main(){
    int n,d[10010];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        t[d[i]]++;
    }
    for(int i=1;i<=n;i++){
        if(t[d[i]]>1){
            cout<<d[i];
            return 0;
        }
    }
    return 0;
}

[此贴子已经被作者于2020-2-26 16:35编辑过]

#11

return_02020-02-26 16:24

回复 9楼叶纤

我个人喜欢能不用数组就不用数组，否则比较慢

#12

return_02020-02-26 16:24

回复 9楼叶纤

可以不用数组呀，不信你试试，效果一样

#13

叶纤2020-02-26 16:28

回复 12楼 return_0

但是题目要求的是数组

#14

叶纤2020-02-26 16:30

回复 3楼纯蓝之刃

我做这几题的时候总卡在一个地方不动了，看看大家的解题思路

#15

return_02020-02-26 16:36

第四题答案：

程序代码：

#include<iostream>
using namespace std;
int t[10000]={0};
int main(){
    int n,d[1000];
    cin>>n;
    for(int i=1;i<=2*n+1;i++){
        cin>>d[i];
        t[d[i]]+=1;
    }
    for(int i=1;i<=2*n+1;i++){
        if(t[d[i]]<2){
            cout<<d[i];
            return 0;
        }
    }
    return 0;
}

#16

return_02020-02-26 16:37

我把第一题改一下哦，

#17

return_02020-02-26 16:38

第一题修改：

程序代码：

#include<iostream>
using namespace std;
int main(){
    int n,s=0,d[10010],u=0;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>d[i];
        u+=d[i];
    }
    for(int i=0;i<=n;i++){
        s+=i;
    }
    cout<<s-u;
    return 0;
}

#18

林月儿2020-02-26 16:40

#19

return_02020-02-26 16:40

第五题答案：

程序代码：

#include<iostream>
using namespace std;
int t[10000]={0};
int main(){
    int n,d[1000];
    cin>>n;
    for(int i=1;i<=2*n+1;i++){
        cin>>d[i];
        t[d[i]]+=1;
    }
    for(int i=1;i<=2*n+1;i++){
        if(t[d[i]]==2){
            cout<<d[i];
            return 0;
        }
    }
    return 0;
}

#20

return_02020-02-26 16:40

好啦，我全答完了

#21

return_02020-02-26 16:40

数据试验过了

#22

叶纤2020-02-26 16:43

回复 20楼 return_0

我评价一下0分

#23

林月儿2020-02-26 16:45

我来评价下，写的挺好的，最后一题判重有点着急了

#24

return_02020-02-26 16:47

答案是对的呀

#25

return_02020-02-26 16:49

是不是要我把cin cout全改成scanf printf呀

#26

return_02020-02-26 16:50

然后把数组全开成动态

#27

return_02020-02-26 16:51

然后把循环2合1？

#28

return_02020-02-26 16:54

回复 14楼叶纤

做这几道题的关键中的关键就是要掌握桶算法

#29

return_02020-02-26 16:55

46分钟，平均每题9分钟

#30

叶纤2020-02-26 17:02

回复 29楼 return_0

对不起，我测试不出来结果，用鲜花补偿你吧

#31

林月儿2020-02-26 17:10

测试用例角度不够，黑盒测试得针对性地多写几个用例

#32

return_02020-02-26 17:13

什么问题呀？也许我能解决呢

1