题解：学而思编程 数字卡片

【题目来源】

学而思编程：数字卡片

【题目描述】

小猴收集了n nn张数字卡片，每一种数字卡片小猴恰好只有一张且都在1 ∼ n 1\sim n1∼n的范围内。

因为小猴加的猫咪贪玩，打翻了装着数字卡片的盒子，经过千辛万苦小猴终于把卡片捡起来装到盒子，但是发现少了一张数字卡片。

已知小猴现在盒子中的卡片分别是a 1 , a 2 , … , a n − 1 a_1,a_2,\dots,a_{n-1}a1​,a2​,…,an−1​，请你帮助小猴找出缺少的那一张数字卡片，并输出对应卡片上的数字。

【输入】

第一行包含一个整数n nn。

第二行包含n − 1 n-1n−1个整数a 1 , a 2 , … , a n − 1 a_1,a_2,\dots,a_{n-1}a1​,a2​,…,an−1​。

【输出】

一行一个整数，表示缺少的是哪一张数字卡片。

【输入样例】

5 4 3 2 1

【输出样例】

5

【核心思想】

1. 问题分析：给定1 11到n nn范围内的n − 1 n-1n−1个互不相同的数字，找出缺失的那个数字。这是一个标记数组问题，关键在于利用值域有限且唯一的特性，通过标记出现过的数字快速定位缺失值。

2. 算法选择：

   • 布尔标记数组：f[i]表示数字i ii是否出现在输入中
   • 线性扫描查找：遍历1 11到n nn，找到未被标记的数字即为缺失值

3. 关键步骤：

   • 初始化：读取n nn
   • 标记出现数字：
     • 遍历i ii从1 11到n − 1 n-1n−1：
       • 读取x xx
       • f[x] = true：标记数字x xx已出现
   • 查找缺失数字：
     • 遍历i ii从1 11到n nn：
       • 若!f[i]（i ii未出现）：输出i ii并结束

4. 时间/空间复杂度：

   • 时间复杂度：O ( n ) O(n)O(n)，两次线性遍历
   • 空间复杂度：O ( n ) O(n)O(n)，布尔标记数组f[1..n]

5. 标记数组的核心思想：

   • 值域确定性：数字范围固定为1 11到n nn，且每个数字恰好出现0 00或1 11次，适合用数组下标直接映射
   • 缺失即未标记：完整集合与给定集合的差集只有一个元素，扫描标记数组即可找到
   • 空间换时间：用O ( n ) O(n)O(n)空间实现O ( n ) O(n)O(n)时间，避免排序或求和的O ( n log ⁡ n ) O(n \log n)O(nlogn)或O ( n ) O(n)O(n)但需处理溢出的方案
   • 扩展性：若值域过大可用unordered_set，但本题值域适中，数组更高效
   • 适用于"有限值域内缺失元素查找"类问题，标记数组是最直观高效的解法

【算法标签】

#模拟

【代码详解】

#include<bits/stdc++.h>usingnamespacestd;boolf[1000005];// 布尔数组，标记出现的数字intmain(){intn;cin>>n;// 输入nfor(inti=1;i<=n-1;i++)// 输入n-1个数{intx;cin>>x;f[x]=true;// 标记x出现过}for(inti=1;i<=n;i++)// 从1到n查找{if(!f[i])// 如果i没出现过{cout<<i;// 输出缺失的数break;// 找到后结束}}return0;}

【运行结果】

5 4 3 2 1 5