LeetCode 136: Single Number

---

Difficulty: Easy

Tags: Hash Table, Bit Manipulation

---

问题描述

一个数组，除了一个数字出现一次外其他都出现了两次，找到这个数字。

---

解决方案

这题可以用按位异或这个技巧很快解决。

因为 A^A = 0，将这个数组里的数字依次按位异或，所有重复出现的数字都会被消去，最后得到的结果就是我们要找的那个数字。

---

▷ Time Complexity: O(n)

▷ Space Complexity: O(1)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int number = nums[0];
      
        for(int i=1; i<nums.size(); i++)
        {
            number ^= nums[i];
        }
      
        return number;
    }
};

---

回到 Conquer Leetcode