leecode 136. Single Number

发表于 | 分类于

题目

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

解法一：

用无序图来存储数据，即m[2] = 1代表数字2在列表中出现了一次。时间复杂度o(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> m;
                //如果这里使用map的话，则为o(nlogn)，因为map查找一次为logn
        for (int i = 0; i < nums.size(); ++i)
        {
            if(m.count(nums[i]))
                m[nums[i]] += 1;
            else
                m[nums[i]] = 1; 
        }
        for(int i = 0; i < nums.size(); ++i)
            if(m[nums[i]] == 1)
                return nums[i];
    }
};

解法二

速度比较快的方法，用位运算可以大大提高运算速度。
xor(异或)的位运算,x ^ x = 0; 0 ^ y = y;

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