136.md

Single Number

题目

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?

思路

解法1： 使用一个set，遍历一次给定的数组，如果该数第一次出现插入set中，如果出现第二次在set中删除，最后返回set的为一个元素就是结果。

//without using extra memory:

解法2: 对给定的数组进行排序，由于只有一个数是single number所以数组长度肯定为单数，single num也只可能出现在索引0,2,4···，两个两个 的检测去遍历数组（除了最后一个元素），如果nums[i]!=nums[i+1]则返回nums[i]否则n+=2。如果前面都是成对出现则最后一个元素肯定是single。

解法3： 使用异或操作符^，对于一个数n 另外一个数A 有：n^A^A = n 这个特性。且异或满足结合律，使用一个result=0的数对数组的每一个元素 异或一次最后的便是结果。

代码

解法1

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int sz = nums.size();
        for(int i=0;i<sz-2;i+=2){
            if(nums[i]==nums[i+1]) continue;
            else return nums[i];
        }
        return nums[sz-1];
    }
};

解法2

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        set<int> s;
        int sz = nums.size();
        for(int i=0;i<sz;++i){
            if(s.find(nums[i])==s.end()){
                s.insert(nums[i]);
            }else{
                s.erase(nums[i]);
            }
        }
               
        return *s.begin();
    }
};

解法3

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