简答题
偏难
#13142
丢失的数字 述给定整数 n 和一个包含 n - 1 个整数的序列,该序列由区间 [1, n] 内的 n - 1 个互异整数组成。请找出该区间内缺失的唯一整数。…
丢失的数字
述给定整数 n 和一个包含 n - 1 个整数的序列,该序列由区间 [1, n] 内的 n - 1 个互异整数组成。请找出该区间内缺失的唯一整数。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:一个整数 n;
第二行:n - 1 个整数。
输出格式
一个整数,表示丢失的数字。
输入样例#1
6 1 2 5 6 3
输出样例#1
4
输入样例#2
10 7 2 3 9 4 8 1 6 10
输出样例#2
5
数据范围:
1≤n≤2×104 ,输入序列保证合法。
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//C语言参考代码
#include <stdio.h>
int a[20001];
int main() {
int i, j, n, min = -1; // 最小数字
scanf("%d", &n);
for (i = 0; i < n - 1; i++) {
int num;
scanf("%d", &num);
if(min == -1)
min = num;
else if(num < min)
min = num;
a[i] = num;
}
for(i=0; i< n - 1; i++) {
bool flag = false;
for(j=0; j<n-1; j++) { // 寻找对应的数字即:min + i
if(min + i == a[j]) {
flag = true;
break;
}
}
if(!flag) {
printf("%d\n", min + i);
break;
}
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//C++参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> vt;
for (int i = 0; i < n - 1; i++) {
int num;
cin >> num;
vt.push_back(num);
}
sort(vt.begin(), vt.end());
int beg = vt[0];
for(int i=0; i<vt.size(); i++, beg++) {
if(vt[i] != beg) {
cout << beg << endl;
break;
}
}
return 0;
}</pre>
这道题暂未补解析。