136. 只出现一次的数字

136. 只出现一次的数字

给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

示例 1 ：

1
2
输入：nums = [2,2,1]
输出：1

示例 2 ：

1
2
输入：nums = [4,1,2,1,2]
输出：4

示例 3 ：

1
2
输入：nums = [1]
输出：1

提示：

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • 除了某个元素只出现一次以外，其余每个元素均出现两次。

解法1：使用哈希表

利用 Hash 表，Time: O(n) Space: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num : nums){
            if (!map.containsKey(num))map.put(num,1);
            else map.remove(num);
        }

        for (Integer key : map.keySet()){
            int value = map.get(key);
            if(value == 1)return key;
        }
        return 0;
    }
}

解法二：使用异或

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        if(nums.length > 1){
            for (int i = 1;i < nums.length ; i ++){
                ans = ans ^ nums[i];
            }
        }
        return ans;
    }
}

解法三：数学

这个是真的牛逼，直接做差就出来了

1
2
3
class Solution(object):
    def singleNumber(self, nums):
        return sum(set(nums))*2 - sum(nums)