【PAT甲級】The Missing Number

• 2019 年 11 月 8 日
• 筆記

版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。

本文鏈接：https://blog.csdn.net/weixin_42449444/article/details/89448094

Problem Description：

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 (≤10​5​​). 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來記錄所有出現在輸入列表中的正整數啊，然後再無腦for循環找出第一個（也就是最小的那個）沒有出現在set中的正整數即可。

AC程式碼：

#include <bits/stdc++.h>  using namespace std;    int main()  {      int N;      cin >> N;      set<int> s;  //用來存放出現過的正整數      for(int i = 0; i < N; i++)      {          int temp;          cin >> temp;          if(temp > 0)  //向set中插入正整數          {              s.insert(temp);          }      }      int ans;   //第一個沒出現過的正整數ans      for(int i = 1; ; i++)      {          if(s.count(i) == 0)  //找到第一個沒出現過的正整數          {              ans = i;              break;          }      }      cout << ans << endl;      return 0;  }