136.只出现一次的数字

Single Number

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

只出现一次.png

题目分析

第一反应是想使用hashmap 等方式来进行求解,遍历map统计出现的次数，最后找出val为1的数即可。但是另一种更高级的做法是使用位运算来解决。
对于任意两个数a和b，我们对其使用 “异或”操作，应该有以下性质：

• 任意数异或0仍为自身： a ^ 0 = a
• 任意数异或自身是 0 ： a ^ a = 0
• 异或操作满足交换律结合律：a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

举个例子 5 ^ 4 ^ 5

算法_只出现一次.png

show code:

//go
func singleNumber(nums []int) int {
    ans := 0
    for _, num := range(nums) {
        ans ^= num
    }
    return ans
}

 //cpp
 class Solution {
 public:
     int singleNumber(vector<int>& nums) {
         int ans = 0;
         for (int num : nums) {
             ans ^= num;
         }
         return ans;
    }
};

 //JAVA
 class Solution {
     public int singleNumber(int[] nums) {
         int ans = nums[0];
         for (int i = 1; i < nums.length; i++) {
             ans = ans ^ nums[i];
         }
         return ans;
     }
}

 //python
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            ans ^= nums[i]
        return ans