算法
(二分) O(logn)
这道题目给定的是递增数组,假设数组中第一个缺失的数是 x,那么数组中的数如下所示;
从中可以看出,数组左边蓝色部分都满足nums[i] == i
,数组右边橙色部分都不满足nums[i] == i
,因此我们可以二分出分界点 x 的值。
另外要注意特殊情况:当所有数都满足nums[i] == i
时,表示缺失的是 n。
时间复杂度分析
二分中的迭代只会执行 O(logn) 次,因此时间复杂度是 O(logn)。
C++ 代码
class Solution {
public:
int getMissingNumber(vector<int>& nums) {
if (nums.empty()) return 0;
int l = 0, r = nums.size() - 1;
while (l < r)
{
int mid = l + r >> 1;
if (nums[mid] != mid) r = mid;
else l = mid + 1;
}
if (nums[r] == r) r ++ ;
return r;
}
};
class Solution { public: int getMissingNumber(vector<int>& nums) { for (int i = 0; i < nums.size(); i++) if (nums[i] != i) return i; return nums.size(); } };
很简练,时间复杂度还有提高空间
边界情况过不去,比如输入【0】
class Solution { public: int getMissingNumber(vector<int>& nums) { if(nums.empty()) { return 0; } for(int i=0;i<=nums.size();i++) { if(nums[i]!=i) { return i; } } } };
改成这个可以ac
你这个有点小问题,如果i = nums.size()的时候,就会越界了
?return nums.size()不是可以
不会吧,肯定有答案吧,所以写while也没事吧
改成i<=nums.size()即可
class Solution { public: int getMissingNumber(vector<int>& nums) { int cnt = 0; for(int x : nums) { if(x == cnt) cnt++; } return cnt; } };
强~~~
6
想不到,太巧妙了
加油hh
有一个办法似乎能避免n缺失,就是初始的时候r=nums.size(),不要−1,这样如果都没有l就会变成r,返回r的时候就是n
class Solution { public: int getMissingNumber(vector<int>& nums) { int l=0,r=nums.size(); while(l<r){ int m=(l+r)>>1; if(nums[m]==m) l=m+1; else r=m; } return l; } };
感觉所有数都满足nums[i] == i 这种特殊情况放在while循环前面判断比较好,这样确保循环是有意义的;
放到前面去确实会好一些hh
class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
for(int i=0;;i++){
if(!count(nums.begin(),nums.end(),i)){
return i;
break;
}
}
}
};
现学现用
class Solution { public: int getMissingNumber(vector<int>& nums) { int sum = 0; for (int i: nums) sum += i; return (1 + nums.size()) * nums.size() / 2 - sum; } };
class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
if(nums.empty())
return 0;
int ans;
int i;
int sum=0;
for (i=0;i<nums.size();i++)
{
sum+=nums[i];
}
int n=nums.size();
int total=n*(n+1)/2;
ans=total-sum;
return ans;
}
};
class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
int i = 0;
for(int x : nums){
if(x != i) break;
else i++;
}
return i;
}
};
这个是不是简单点
n很大的话容易tle
彩
为啥这个题二分的执行时间还不如直接遍历
因为存在缺失的数字就是第一个的情况,直接遍历O(1)就出了,而二分得log(n).
数据很大的时候二分还是很好的
if (nums[r] == r) r ++ ;
为什么r要++啊?懂了,特判缺失是n的情况
这个时间复杂度是怎么分析的?有大佬教教吗?
如果一开始r设定为nums.size()就不需要特判了
auto a=nums.begin();
int i;
for( i=0;i<nums.size();i++)
{
if(nums[i]!=i) break;
}
return i;
自己推了一遍 思路Tql
y总,题目中说的是长度为 n−1 的递增排序数组,所以数组下标 应该是到n-2,数组中的值到n-1
首先求出最后一个节点是多少(设它为n)在求出从1加到n的值(设为b),然后求出输入值的和(设为c),输出b - c
class Solution {
public:
int getMissingNumber(vector[HTML_REMOVED]& nums) {
if(nums.empty()) return 0;
int l = 0,r = nums.size()-1;
while(l[HTML_REMOVED]>1;
if(nums[mid]!=mid) r = mid-1;
else l = mid+1;
}
if(nums[r]==r)r++; return r; }
};
class Solution { public: int getMissingNumber(vector<int>& nums) { int n=0; for(int x:nums) { if(n!=x) break; n++; } return n; } };
😆
👍
%
如果取值很大的话,容易TLE
写成了r=mid-1,结果错了
强