single-number

Single Number – LeetCode 136

Problem

Description

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Answer

Original

Code

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

思路

使用异或操作，妙啊，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$13$ ms，排名$52.03\%$

Better

思路

还没看到更好的解法。