LeetCode 268. Missing Number(消失的数字)
题目描述
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
Example 1
Input: [3,0,1]
Output: 2
Example 2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
解法一
思路
这题其实就是LeetCode 136. Single Number(只出现一次的数)的马甲。
这题换个说法就是0, 1, 2, ..., n
中除了一个数仅出现一次外,其他数都出现了两次,求这个仅出现一次的数。那么就是异或扫一遍了。
Python
class Solution(object):
def missingNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for i in range(0, len(nums)):
result ^= i
result ^= nums[i]
result ^= len(nums)
return result
Java
public class Solution {
public int missingNumber(int[] nums) {
int result = 0;
for (int i = 0; i < nums.length; i++) {
result ^= i;
result ^= nums[i];
}
result ^= nums.length;
return result;
}
}
C++
class Solution {
public:
int missingNumber(vector<int> &nums) {
int result = 0;
for (int i = 0; i < nums.size(); i++) {
result ^= i;
result ^= nums[i];
}
result ^= nums.size();
return result;
}
};