Single Number III

Problem

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

• The order of the result is not important. So in the above example, [5, 3] is also correct.
• Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

Solution

Hash Set Solution: O(n) time, O(n) space

public class Solution {
    public int[] singleNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) set.remove(num);
        }
        return set.stream().mapToInt(i -> i).toArray();
    }
}

Analysis

In the Hash Set solution, we remove the element if we cannot add it (means appearing twice)
Then we convert set to in[] by calling set.stream().mapToInt(i -> i).toArray()

In the Bit Manipulation solution:
//To be continued