268. Missing Number - Easy

前往題目

想法

• 只想到了用HashSet存，然後比較，雖然是時間是O(N)但空間也是，不符合題目要求

思路

這題大致有兩種做法，Bit manipulation和Sum

Bit manipulation

1. 算0~n的XOR應該是多少
2. 再用上面的結果去XOR實際的nums陣列
3. 因為XOR的特性是與自己相同的XOR完會是0，所以全部XOR一遍的結果就是答案，也就是缺失的那個

Sum

1. 可以用公式直接算出0~n的總和
2. 然後再算nums的總和，互減之後就是答案

Code

自己寫的，TimeO(N)，SpaceO(N)

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> exist = new HashSet();

        for (int i = 0; i < nums.length; ++i) {
            exist.add(nums[i]);
        }

        for (int i = 0; i < nums.length; ++i) {
            if (!exist.contains(i)) {
                return i;
            }
        }
        return nums.length;
    }
}

Bit manipulation

class Solution {
    public int missingNumber(int[] nums) {
        // Because we can iterate until nums[nums.length]
        // So we put its length first
        int res = nums.length;

        for (int i = 0; i < nums.length; ++i) {
            // XOR theoretically number
            res ^= i;
            // XOR the number in the array
            res ^= nums[i];
        }

        return res;
    }
}