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;
    }
};