本文介绍: 根据题目给定的样例及陈述,在代码实现中可定义一个递增的动态数组 v。
【题目来源】
https://www.acwing.com/problem/content/64/
【题目描述】
一个长度为 n−1 的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围 0 到 n−1 之内。
在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中,请找出这个数字。
【输入样例】
0 1 2 4
【输出样例】
3
【数据范围】
1≤n≤1000
【算法分析】
以下算法思路来源于:https://www.acwing.com/solution/content/1261/
根据题目给定的样例及陈述,在代码实现中可定义一个递增的动态数组 v。
假设动态数组 v 中第一个缺失的数是 x,则其中的各数对应关系如下图所示。
从图中可以看出,数组左边蓝色部分都满足 v[i] == i,数组右边橙色部分都不满足 v[i] == i,因此我们可以二分出分界点 x 的值。
另外要注意特殊情况:当所有数都满足 v[i] == i 时,表示缺失的是 n。
【算法代码】
#include <bits/stdc++.h>
using namespace std;
int getMissingNumber(vector<int>& v) {
if(v.empty()) return 0;
int le=0;
int ri=v.size()-1;
while(le<ri) {
int mid=(le+ri)>>1;
if(v[mid]!=mid) ri=mid;
else le=mid+1;
}
if(v[ri]==ri) ri++;
return ri;
}
int main() {
vector<int> v;
int x;
while(cin>>x) {
v.push_back(x);
}
cout<<getMissingNumber(v)<<endl;
return 0;
}
/*
in:0 1 2 3 4 6
out:5
*/
【参考文献】
https://www.acwing.com/solution/content/1261/
原文地址:https://blog.csdn.net/hnjzsyjyj/article/details/135711779
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_58958.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。