卖萌的弱渣

I am stupid, I am hungry.

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

n nums = [0, 1, 3] return 2.

Note

Yourlgorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

Solution

  • X ^ 0 ^ X = 0
  • X ^ 0 = X
  • Java
(Missing-Number.java) download
1
2
3
4
5
6
7
8
9
10
11

public class Solution {
    public int missingNumber(int[] nums) {
        int xor = 0;
        int i;
        for (i=0;i<nums.length; i++){
            xor = xor ^ i;
            xor = xor ^ nums[i];
        }
        return xor ^ i;
    }
}
  • Python
(Missing-Number.py) download
1
2
3
4
5
6
7
8
9
10
11
12

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        xor = 0
        for i in range(len(nums)):
            xor ^= i
            xor ^= nums[i]
        # because there is one missing
        return xor^len(nums)