136. 只出現一次的數字

給你一個 非空 整數數組 nums ，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

你必須設計並實現線性時間複雜度的算法來解決此問題，且該算法只使用常量額外空間。

 

示例 1 ：

輸入：nums = [2,2,1]

輸出：1

示例 2 ：

輸入：nums = [4,1,2,1,2]

輸出：4

示例 3 ：

輸入：nums = [1]

輸出：1

 

提示：

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某個元素只出現一次以外，其餘每個元素均出現兩次。
class Solution {
    public int singleNumber(int[] nums) {
        int ans = 0;
        for (int x : nums) {
            ans ^= x;
        }
        return ans;
    }
}137. 只出現一次的數字 II

137. 只出現一次的數字 II

給你一個整數數組 nums ，除某個元素僅出現 一次 外，其餘每個元素都恰出現 三次 。請你找出並返回那個只出現了一次的元素。

你必須設計並實現線性時間複雜度的算法且使用常數級空間來解決此問題。

 

示例 1：

輸入：nums = [2,2,3,2]
輸出：3

示例 2：

輸入：nums = [0,1,0,1,0,1,99]
輸出：99

 

提示：

  • 1 <= nums.length <= 3 * 104
  • -231 <= nums[i] <= 231 - 1
  • nums 中，除某個元素僅出現 一次 外，其餘每個元素都恰出現 三次
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            int num = entry.getKey(), occ = entry.getValue();
            if (occ == 1) {
                ans = num;
                break;
            }
        }
        return ans;
    }
}