Leetcode #137 Single Number II

[yokostan]

My solution (HashMap), O(n), runtime beats 11%:

class Solution {
    public int singleNumber(int[] nums) {
        int res = nums[0];
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            }
            else {
                map.put(nums[i], 1);
            }
        }

        for (int n : map.keySet()) {
            if (map.get(n) == 1) {
                res = n;
            }
        }

        return res;
    }
}

Bit Manipulation, runtime O(1):

class Solution {
    public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
    }
}

https://leetcode.com/problems/single-number-ii/discuss/167343/topic