137. 隻出現一次的數字 II（Java）（面試題56 - II. 數組中數字出現的次數 II）（HashSet求非重複元素和）（HashMap value記錄元素是否重複）

1 題目

給定一個非空整數數組，除了某個元素隻出現一次以外，其餘每個元素均出現了三次。找出那個隻出現了一次的元素。

說明：

你的算法應該具有線性時間複雜度。 你可以不使用額外空間來實作嗎？

示例 1:

輸入: [2,2,3,2]

輸出: 3

示例 2:

輸入: [0,1,0,1,0,1,99]

輸出: 99

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/single-number-ii

著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2 Java

2.1 ！方法一（HashSet）

由于其它元素出現了三次，不能通過将碰到第二次的元素從set中删除以獲得僅出現一次的元素

通過元素總和sumArray、非重元素總和sumSet，來計算出僅出現一次的元素值

class Solution {
    public int singleNumber(int[] nums) {
        HashSet<Long> set = new HashSet<>();
        long sumArray = 0, sumSet = 0;
        
        for(long num: nums){
            set.add(num);
            sumArray += num;
        }
        for(long s: set) sumSet += s;

        return (int)((3 * sumSet - sumArray) / 2);
    }
}
           

2.2 方法二（HashMap）

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

        for(int i = 0; i < nums.length; i++){
            // 該元素已出現過，value=1
            if(map.containsKey(nums[i]))    map.put(nums[i], 1);
            // 該元素未出現過，value = 0
            else    map.put(nums[i], 0);
        }

        // 周遊map，找到出現一次的元素（value == 0）
        // for(int key: map.keySet()){
        //     if(map.get(key) == 0)   return key;
        // }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue() == 0)    return entry.getKey();
        }

        return -1;
    }
}
           

2.3 ！方法三（位運算）

第一次出現，seenOnce儲存，seenTwice沒有

第二次出現，seenOnce沒有，seenTwice儲存

第三次出現，都沒有

class Solution {
    public int singleNumber(int[] nums) {
        int seenOnce = 0, seenTwice = 0;

        for(int num: nums){
            seenOnce = (~seenTwice) & (seenOnce^num);
            seenTwice = (~seenOnce) & (seenTwice^num);
        }
        
        return seenOnce;
    }
}