Single Number

easy 原题链接：https://leetcode.com/problems/single-number/

Single Number

原题链接

描述

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?

例子

Input: [2,2,1]

Output: 1

解法 快慢指针 answer wrong 6/16

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res=0, fastres=1;
        while(res<fastres&&fastres<nums.size()){
            if(nums[res]==nums[fastres]){
                res=res+2;
                fastres=res+1;
            }else{fastres++;}
        }
        return nums[res];
    }
};

解法 HashTable

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> hash_table;
        for(int i:nums){
            hash_table[i]++;
        }
        for(auto m:hash_table){
            if(m.second==1){
                return m.first;
            }
        }
        return 0;
    }
};

解法 math

2∗(a+b+c)−(a+a+b+b+c)=c

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sumOfset=0, sumOfNums=0;
        unordered_set<int> seen;
        for(int num: nums){
            if(!seen.count(num)){
                seen.insert(num);
                sumOfset+=num;
            }
            sumOfNums+=num;
        }
        return 2*sumOfset-sumOfNums;
    }
};

解法binary

Concept

• If we take XOR of zero and some bit, it will return that bit

  • a ⊕0 = a

• If we take XOR of two same bits, it will return 0

  • a⊕a=0

• a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR all bits together to find the unique number.

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a=0;
        for(int i:nums){
            a ^= i;
        }
        return a;
    }
};