136.Single Number

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：
字数统计: 378 | 阅读时间 ≈ 1

题目描述

Given a non-empty 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?

Example 1:
Input: [2,2,1]
Output: 1

Example 2:
Input: [4,1,2,1,2]
Output: 4

我的解法

解题思路

可以先将数组进行排序，再和两边的数字进行比较，如果都不一样就是要找的的数字。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        if (nums.size() == 1)
            return nums[0];
        sort(nums.begin(),nums.end());
        if (nums[0] != nums[1])
            return nums[0];
        for (int i = 1; i < nums.size()-1; i++){
            if (nums[i] != nums[i+1] && nums[i] != nums[i-1])
                return nums[i];
        }
        return nums[nums.size()-1];
    }
};

Runtime: 20 ms, faster than 37.49% of C++ online submissions for Single Number.
Memory Usage: 9.7 MB, less than 53.92% of C++ online submissions for Single Number.

高票解法

速度还是稍微慢了点的，看看高票的解法吧～
看到有好巧妙的方法，比如用按位异或的方法。因为相同的数字异或是等于0的，并且一个数和0异或的结果还是这个数，异或也符合交换律。所以将数组里的数全部按位异或，最后就可以得到只出现一次的数字了。

实现代码

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

Runtime: 16 ms, faster than 73.30% of C++ online submissions for Single Number.
Memory Usage: 9.6 MB, less than 82.15% of C++ online submissions for Single Number.