题意概述
- 从0~n中按序给定n个数
- 要求找出0~n中缺失的数
方法一:求和公式
思路与具体做法
- 等差公式求前n项和n*(n+1)/2
- 再累加整个数组的值
- 两个相减就是所缺失数字
class Solution {
public:
int solve(vector<int>& a) {
int sum=0,n=a.size();
for(int i=0;i<n;i++){
sum+=a[i];
}
return n*(1+n)/2-sum;
}
};
时间复杂度和空间复杂度分析
- 时间复杂度:O(n),遍历了一遍数组
- 空间复杂度:O(1),仅定义了一个整形变量sum
方法二:位运算
思路与具体做法
- 遍历整个数组,将所有元素异或,因为出现两次的元素异或为0,最后就剩下了出现一次的元素
- a⊕a=0:相同的两个数异或为0
- a⊕0=a:任意数和0异或为其本身
- a⊕b⊕c=a⊕c⊕b:异或具有交换律
class Solution {
public:
int solve(vector<int>& a) {
int sum=0,n=a.size();
for(int i=0;i<n;i++){
sum^=a[i]^(i+1);
}
return sum;
}
};
时间复杂度和空间复杂度分析
- 时间复杂度:O(n),遍历了一遍数组
- 空间复杂度:O(1),仅定义了一个整形变量sum