137. Single Number II.md

137. Single Number II

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99

Code

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for num in nums:
            dic[num] = dic.get(num,0)+1
        for key,val in dic.items():
            if val == 1:
                return key

Code-Java

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num : nums)
        {
            if(map.get(num)==null)
                map.put(num,1);
            else
                map.replace(num,map.get(num)+1);
        }
        int result = -1;
        for(int k : map.keySet())
            if(map.get(k)==1)
            {
                result = k;
                break;
            }
        return result;
        
    }
}