国外室内设计网站推荐,养老网站建设方案,郑州网站建设哪家最好,网站什么认证对做电商好【题目来源】https://www.acwing.com/problem/content/64/【题目描述】 一个长度为 n−1 的递增排序数组中的所有数字都是唯一的#xff0c;并且每个数字都在范围 0 到 n−1 之内。 在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中#xff0c;请找出这个数字。【…【题目来源】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(vectorint v) {if(v.empty()) return 0;int le0;int riv.size()-1;while(leri) {int mid(leri)1;if(v[mid]!mid) rimid;else lemid1;}if(v[ri]ri) ri;return ri;
}int main() {vectorint v;int x;while(cinx) {v.push_back(x);}coutgetMissingNumber(v)endl;return 0;
}/*
in:0 1 2 3 4 6
out:5
*/
【参考文献】https://www.acwing.com/solution/content/1261/
