给定一个包含 0, 1, 2, ..., n 中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
示例 1:
输入: [3,0,1]
输出: 2
示例2:
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
func missingNumber(nums []int) int {
// 因为没有跳过的数,所以求出长度的和,然后减去每一项的值
max := len(nums) * (len(nums) + 1) / 2
for _, j := range nums {
max -= j
}
return max
}
解法2
解法2
func missingNumber(nums []int) int {
xor := 0
for i, n := range nums {
xor ^= i ^ n
}
// 所有的 i 再加上 len(nums),就相当于 0,1,...,n。
// 利用 相同的数异或为0,及其交换律
// xor 最后的值,就是那个缺失的数
return xor ^ len(nums)
}
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。