/*the SUM of Arithmetic sequence */
public class Solution {
public int missingNumber(int[] nums) {
int len = nums.length;
int sum = (0 + len)*(len + 1) / 2;
for(int i = 0; i < nums.length; i++){
sum -= nums[i];
}
return sum;
}
}
/*If the array is in order, I prefer Binary Search method. Otherwise, the XOR method is better.*/
public int missingNumber(int[] nums) { //binary search
Arrays.sort(nums);
int left = 0, right = nums.length, mid= (left + right)/2;
while(left<right){
mid = (left + right)/2;
if(nums[mid]>mid) right = mid;
else left = mid+1;
}
return left;
}
/*XOR*/
/* 参与运算的两个值,如果两个相应位相同,则结果为0,否则为1。即:
0^0=0, 1^0=1, 0^1=1, 1^1=0
0^0=0,0^1=1 可以看出,0异或任何数=任何数
1^0=1,1^1=0 可以看出 1异或任何数=任何数取反
任何数异或自己=把自己置0
数a两次异或同一个数b(a=a^b^b)仍然为原值a.
*/
public int missingNumber(int[] nums) { //xor
int res = nums.length;
for(int i=0; i<nums.length; i++){
res ^= i;
res ^= nums[i];
}
return res;
}
/*举个例子,比如,我们得到一个数组[0,1,2,4,5],则res==5,在每一次for循环中,我们让5分别和i、nums[i]做异或运算,在5次循环后,res会和数列[0,1,2,3,4]和数组[0,1,2,4,5]都异或一遍,因为一个数a两次异或同一个数b(a=a^b^b)仍然为原值a,所以,初始值5在多次异或运算后,得到的结果就是只与5异或一次的数字,也就是缺的哪一个数字。
这种方法运用了位运算,计算十分快。*/
/*TESTCASES:
Intput:
[0]
[0,1,3]
[1,0]
Output:
1
2
2
*/