LeetCode 268. 丢失的数字
题目描述
思路分析
方法一：数学方法
根据等差数列求和公式，可以求出 0 到 n 的和，然后减去给定序列的和，剩下的就是缺失的数字。
方法二：异或运算
利用异或运算的性质，即 a^b^b=a，可以将序列中的所有数字和 0 到 n 中的所有数字依次异或，最后剩下的就是缺失的数字。
方法三：二分查找
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
func missingNumber(nums []int) int {
sort.Ints(nums)
left, right := 0, len(nums) - 1
for left <= right {
mid := left +(right - left)/2
if nums[mid] > mid {
right = mid - 1
} else {
left = mid + 1
}
}
return left
}
1
2
3
4
5
6
7
8
func missingNumber(nums []int) int {
res := len(nums)
for i, num := range nums {
res ^= i
res ^= num
}
return res
}
1
2
3
4
5
6
7
8
9
func missingNumber(nums []int) int {
n := len(nums)
total := (1 + n) * n / 2
sum := 0
for _, num := range nums {
sum += num
}
return total - sum
}
1
write your code here
相似题目
| 题目 | 难度 | 题解 |
|---|---|---|
| 缺失的第一个正数 | Hard | |
| 只出现一次的数字 | Easy | |
| 寻找重复数 | Medium | |
| 情侣牵手 | Hard |
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！