136. Single Number

二刷 06/2022

Version #1 Bit Manipulation

• If we take XOR of zero and some bit, it will return that bit
  • $a \oplus 0 = a$
• If we take XOR of two same bits, it will return 0
  • $a \oplus a = 0$
• $a \oplus b \oplus a = (a \oplus a) \oplus b = 0 \oplus b = b$

Time O(N)

Space O(1)

Runtime: 2 ms, faster than 60.75% of Java online submissions for Single Number.

Memory Usage: 50.7 MB, less than 42.75% of Java online submissions for Single Number.

class Solution {

    public int singleNumber(int[] nums) {

        if (nums == null || nums.length == 0) {

            throw new IllegalArgumentException("input cannot be empty");

        }

        int result = 0;

        for (int num : nums) {

            result ^= num;

        }

        return result;

    }

}

一刷
31.91 %
class Solution {
    public int singleNumber(int[] nums) {
        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        return xor;
    }
}