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

【题目来源】学而思编程数字卡片【题目描述】小猴收集了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 11到n nn范围内的n − 1 n-1n−1个互不相同的数字找出缺失的那个数字。这是一个标记数组问题关键在于利用值域有限且唯一的特性通过标记出现过的数字快速定位缺失值。算法选择布尔标记数组f[i]表示数字i ii是否出现在输入中线性扫描查找遍历1 11到n nn找到未被标记的数字即为缺失值关键步骤初始化读取n nn标记出现数字遍历i ii从1 11到n − 1 n-1n−1读取x xxf[x] true标记数字x xx已出现查找缺失数字遍历i ii从1 11到n nn若!f[i]i ii未出现输出i ii并结束时间/空间复杂度时间复杂度O ( n ) O(n)O(n)两次线性遍历空间复杂度O ( n ) O(n)O(n)布尔标记数组f[1..n]标记数组的核心思想值域确定性数字范围固定为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但本题值域适中数组更高效适用于有限值域内缺失元素查找类问题标记数组是最直观高效的解法【算法标签】#模拟【代码详解】#includebits/stdc.husingnamespacestd;boolf[1000005];// 布尔数组标记出现的数字intmain(){intn;cinn;// 输入nfor(inti1;in-1;i)// 输入n-1个数{intx;cinx;f[x]true;// 标记x出现过}for(inti1;in;i)// 从1到n查找{if(!f[i])// 如果i没出现过{couti;// 输出缺失的数break;// 找到后结束}}return0;}【运行结果】5 4 3 2 1 5