136. Single Number

發表於 | 分類於

problem

  • 給定一維整數陣列，找出那個single number，假設其他數字皆會出現兩次

solution

option 1 - hash table

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> m;
        for(int n:nums) m[n]++;
        for(int n:nums){
            if(m[n]==1) return n;
        }
        return -1;
    }
};

set/map find operation better than count operation, find 找到就return ，count則會繼續拜訪。

option 2 - Bit Manipulation

  • 善用 x^x=0特性 以及 XOR交換率
1
2
3
4
5
6
7
8
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for(int n:nums) ret^=n;
        return ret;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)