[11]序列找数-招商银行信用卡中心2018秋

1.题目描述

从非负整数序列 0, 1, 2, ..., n 中给出包含其中 n 个数的子序列，请找出未出现在该子序 列中的那个数。

• 输入描述:
  输入为 n+1 个非负整数，用空格分开。
  其中：首个数字为非负整数序列的最大值 n，后面 n 个数字为子序列中包含的数字。
• 输出描述:
  输出为 1 个数字，即未出现在子序列中的那个数。
• 输入示例:

  3 3 0 1 
  

• 输出示例:

  2
  

2.题目解析

最简单的方式就是两层循环嵌套，进行查找。

3.参考答案

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 0;
   scanf("%d",&n);
   int nums[n];
   fill_n(nums,n,0);
   for(int i=0;i<n;++i){
       scanf("%d",&nums[i]);
   }
   for(int i=0;i<=n;++i){
       bool has = false;
       for(int j=0;j<n;++j){
           if(i == nums[j]){
               has = true;
               break;
           }
       }
       if(has == false){
           printf("%d\n",i);
           break;
       }
   }
   return 0;
}

使用STL的find()简化

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 0;
   scanf("%d",&n);
   int nums[n];
   fill_n(nums,n,0);
   for(int i=0;i<n;++i){
       scanf("%d",&nums[i]);
   }
   for(int i=0;i<=n;++i){
       if(find(nums,nums+n,i) == nums+n){
           printf("%d\n",i);
           break;
       }
   }
   return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 0;
   scanf("%d",&n);
   int sum = 0;
   for(int i=0;i<n;++i){
       int n = 0;
       scanf("%d",&n);
       sum += n;
   }
   int sum_n = 0;
   for(int i=0;i<=n;++i){
       sum_n += i;
   }
   printf("%d\n",sum_n - sum);   
   return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 0;
   scanf("%d",&n);
   int sum = 0;
   for(int i=0;i<n;++i){
       int n = 0;
       scanf("%d",&n);
       sum += n;
   }
   int sum_n = n*(n+1)/2; // 等差数列求和公式
   printf("%d\n",sum_n - sum);   
   return 0;
}

牛客题目