curTain

  1. 缺失数字

268. 缺失数字

给定一个包含 0, 1, 2, …, n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2
示例 2:

输入: [9,6,4,2,3,5,7,0,1]
输出: 8

解法一 高斯求和公式

使用数学解法:

  1. 利用高斯求和公式求出序列长度值总和
  2. 遍历数列,求出现有总和
  3. 相减得差

可知,和为 0 到 n 的和,
高斯求和公式:总个数 / 2 * ( 最小的数 + 最大的数 )

实现

1
2
3
4
5
6
7
8
9
10
var missingNumber = function(nums) {
// 因为缺失了一个数,所以长度要加一,
// 最大的数就是数组的长度那个数,那个数加上 0
let allcount = ( nums.length + 1 ) / 2 * ( nums.length + 0 )
let res = 0
for( let i = 0; i < nums.length; i ++ ){
res += nums[i]
}
return allcount - res
};

解法二 位运算

异或运算满足结合律,两个相同的数异或运算返回 0,不相同的数异或返回原来的数

异或运算的真值表:

a b a^b
0 0 0
0 1 1
1 0 1
1 1 0

案例:

1^1 // 0
1^2 // 3 10^1 -> 11 -> 2+1=3
4^5 // 1 4->100 5->101 100^101 -> 001 -> 1

解释:会把数字转换为二进制,再进行异或运算

案例:

有这样的案例:

|下标|0|1|2|3|
|–|–|–|–|
|数字|0|1|3|4|

得到公式:4^(0^0)^(1^1)^(2^3)^(3^4)
交换律: = (4^4)^(0^0)^(1^1)^(3^3)^2
最后结果:= 0^0^0^0^2
= 2

实现

1
2
3
4
5
6
7
var missingNumber = function(nums) {
let n = nums.length
for( let i = 0; i < nums.length; i ++ ){
n ^= nums[i] ^ i
}
return n
};

总结

当涉及到数字运算时,可以优先考虑数学公式和位运算


 评论