C++题目:丢失的数字

题目描述

给你m个1到n之间的整数,你能找出1到n中的哪些整数没有出现吗?

输入

第一行2个整数n,m,直接用空格分隔(1 <= n <= 100000, m < n),表示有m个1到n之间的整数。 接下来m行,每行一个整数ai(1 <= ai <=n,数据保证m个数都不相同)。

输出

每行1个数,从小到大输出输入数据中没有出现过的1到n中的整数。

样例输入

5 3

3

1

4

样例输出

2

5

问题分析

这是程序设计课堂上的一个测验题,我拿到这个题目时,就已经有想法了:把输入的ai存在一个数组a中,再把1到n按照顺序存到数组b中,用嵌套循环遍历数组a和数组b,将数组b中与a相同的数字标记为0,最后输出数组b中非0的数。没错,最后超时了,效率太低。 附上最初的代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<iostream>
#include<algorithm>

using namespace std;

int main()
{
    int n , m , i;
    cin >> n >> m;
    int a[m],b[n];
    for(i = 1;i <= n;i++)
    {
        b[i - 1] = i;
    }
    for(i = 0;i < m;i++)
    {
        cin >> a[i];
    }
    for(i = 0;i < m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            if(a[i] == j)
            {
                b[j - 1] = 0;
            }
        }
    }
    for(i = 0;i < n;i++)
    {
        if(b[i] != 0)
        {
            cout << b[i] << endl;
        }
    }
    return 0;
}

后来想了许久,发现可以只用一个数组,并不需要数组b,只需要一个数组a,n+1个元素,并全部初始化为0,输入ai时,将数组a对应下标(ai)的元素的值改为1,最后下标从1开始,输出a中为0的元素的下标即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>

using namespace std;

int main()
{
    int n,m,i,cnt;
    cin >> n >> m;
    int a[n + 10] = {0};
    for(i = 0;i < m;i++)
    {
        cin >> cnt;
        a[cnt] = 1;
    }
    for(i = 1;i <= n;i++)
    {
        if(a[i] == 0)
        {
            cout << i << endl;
        }
    }
    return 0;
}