137. 隻出現一次的數字 II

2021-04-30 LeetCode每日一題

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

方法1：使用map記錄每個數出現的次數，再找出出現一次的數即可。

時間複雜度O(n)，空間複雜度O(n)

class Solution {
    int res = 0;
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        map.forEach((key, value) -> {
            if (value == 1) {
                res = key;
            }
        });

        return res;
    }
}
           

方法2：每位數轉換為32位的二進制，使用一個長度為 32 的數組 cnt[]記錄下所有數值的每一位共出現了多少次 1，再對 cnt[]數組的每一位進行 mod 3 操作，重新拼湊出隻出現一次的數值。

考慮樣例 [1,1,1,3]，1和 3 對應的二進制表示分别是 00…001 和 00…011，存入 cnt[] 數組後得到 [0,0,…,0,1,4]。進行 mod3 操作後得到 [0,0,…,0,1,1]，再轉為十進制數字即可得「隻出現一次」的答案 3。

時間複雜度O(n)，空間複雜度O(1)

class Solution {
    public int singleNumber(int[] nums) {
        int[] count = new int[32];
        int len = nums.length, res = 0;
        
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < 32; j++) {
                if (((nums[i] >> j) & 1) == 1) {
                    count[j]++;
                }
            } 
        }

        for (int i = 0; i < 32; i++) {
            if (count[i] % 3 == 1) {
                res += (1 << i);
            }
        }

        return res;
    }
}