【PAT甲级 - C++题解】1144 The Missing Number

简介: 【PAT甲级 - C++题解】1144 The Missing Number

1144 The Missing Number

Given N integers, you are supposed to find the smallest positive integer that is NOT in the given list.


Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤105). Then N integers are given in the next line, separated by spaces. All the numbers are in the range of int.


Output Specification:

Print in a line the smallest positive integer that is missing from the input list.


Sample Input:

10
5 -25 9 6 1 3 4 2 5 17

Sample Output:

7


题意

给定一个数组,找到其中未出现的最小正整数。

思路

我们可以将所有数存进一个 set 容器,它会自动帮我们去掉重复的数字并排序,然后再从 1 往后查找,第一个没有在 set 中找到的数字就是我们要找的最小正整数。


代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100000;
unordered_set<int> res;
int main()
{
    int n;
    cin >> n;
    //将正数放入容器
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        res.insert(x);
    }
    //找到最小未出现的正整数
    int t;
    for (t = 1; t <= N; t++)
    {
        if (res.count(t) == 0)
        {
            cout << t << endl;
            return 0;
        }
    }
    cout << t << endl;
    return 0;
}
目录
相关文章
|
C++
【PAT甲级 - C++题解】1040 Longest Symmetric String
【PAT甲级 - C++题解】1040 Longest Symmetric String
64 0
|
算法 C++
【PAT甲级 - C++题解】1044 Shopping in Mars
【PAT甲级 - C++题解】1044 Shopping in Mars
81 0
|
C++
【PAT甲级 - C++题解】1117 Eddington Number
【PAT甲级 - C++题解】1117 Eddington Number
75 0
|
存储 C++ 容器
【PAT甲级 - C++题解】1057 Stack
【PAT甲级 - C++题解】1057 Stack
73 0
|
存储 C++
【PAT甲级 - C++题解】1055 The World‘s Richest
【PAT甲级 - C++题解】1055 The World‘s Richest
76 0
|
C++
【PAT甲级 - C++题解】1051 Pop Sequence
【PAT甲级 - C++题解】1051 Pop Sequence
76 0
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
98 1
|
5月前
|
存储 SQL 算法
LeetCode 题目 65:有效数字(Valid Number)【python】
LeetCode 题目 65:有效数字(Valid Number)【python】
|
6月前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
42 0
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
38 0