缺失數(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)?
思路
- 直接求和,將n到0的和減去當(dāng)前數(shù)組求和即為缺的數(shù)字
- 使用異或.aabbc=c
代碼
//直接求和
class Solution {
public int missingNumber(int[] nums) {
if(nums.length == 0){
return -1;
}
int sum = 0;
int nMax = nums.length;
for(int i = 0;i < nums.length;i++){
sum+=nums[i];
}
int result = (1+nMax)*nMax/2-sum;
return result;
}
}
異或
public int missingNumber(int[] nums) {
//因為數(shù)字從0-n少一個，而數(shù)組下標(biāo)是從0-n-1，只需要添加一個n籽暇，全部異或即可(添加0窘行，異或i+1亦可)
int res=nums.length;
for (int i = 0; i < nums.length; i++) {
res=res^nums[i];
res=res^i;
}
return res;
}
