268. 缺失數(shù)字
描述
- 給定一個包含 0, 1, 2, ..., n 中 n 個數(shù)的序列，找出 0 .. n 中沒有出現(xiàn)在序列中的那個數(shù)茶宵。
示例
示例 1:
輸入: [3,0,1]
輸出: 2
示例 2:
輸入: [9,6,4,2,3,5,7,0,1]
輸出: 8
說明: 你的算法應(yīng)具有線性時間復(fù)雜度倍踪。你能否僅使用額外常數(shù)空間來實現(xiàn)?
思路
- 求和公式求出等差數(shù)列的和梯捕，然后計算出數(shù)組的和匙瘪，兩者之差就是缺失的數(shù)字铆铆。
- 一個數(shù)與自身作異或操作等于0，因此可以將0~n的異或結(jié)果異或上nums[0]到nums[n-1]的異或結(jié)果丹喻，計算的答案就是缺失的數(shù)字薄货。
class Solution_268_01 {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size();
int sum = n * (n + 1) / 2;
int total = 0;
// 下面的 for 循環(huán)可以利用標(biāo)準(zhǔn)庫算法計算
// int total = std::accumulate(nums.begin(), nums.end(),0);
for (int num : nums) {
total += num;
}
return sum - total;
}
};
class Solution_268_02 {
public:
int missingNumber(vector<int>& nums) {
int n = nums.size(), ret = 0;
// 此處 從 n 異或到 1，從nums[n-1] 異或到 nums[0],剩下的就是缺少的那個數(shù)
while (n) ret ^= (n--) ^ nums[n];
return ret;
}
};
