260. Single Number III

一刷 07/2022

Version #1 Bitmask

i & (-i) 可以找到i从右向左看的第一个'1' bit

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 100.00% of Java online submissions for Single Number III.

Memory Usage: 45.6 MB, less than 26.86% of Java online submissions for Single Number III.

class Solution {

    public int[] singleNumber(int[] nums) {

        int bitmask = 0;

        for (int num : nums) {

            bitmask ^= num;

        }

        // The right most bit of one single number

        int diff = bitmask & (-bitmask);

        int x = 0;

        for (int num : nums) {

            if ((num & diff) != 0) {

                x ^= num;

            }

        }

        

        return new int[]{x, bitmask ^ x};

    }

}