0136._Single_Numbe.md

136. Single Numbe

难度:Easy

刷题内容

原题连接

• https://leetcode.com/problems/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?

Example 1:

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

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

思路1 - 时间复杂度: O(n)- 空间复杂度: O(1)******

用异或运算解决这道题，这里用了异或运算的几个性质，异或的交换和结合律，还有两个相同的数异或的值为0，任何数异或0为它本身。有了这些基本只是之后，我们只要对数组进行异或运算得到的数就是答案。因为只有一个数是 single number，其余的数都成双，那么最后就相当于single number异或0

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

思路2 - 时间复杂度: O(n)- 空间复杂度: O(1)******

第二种思路将所有数转成二进制，记录下每一位不为2的倍数，这些位为1，其余为0，求出最后的数就是答案。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
         int arr[32][2],t = 1;
        memset(arr,0,sizeof(arr));
        for(int i = 0;i < nums.size();++i)
        {
            int count1 = 0;
            if(nums[i] < 0)
            {
                t *= -1;
                nums[i] *= -1;
            }
            while(nums[i])
            {
                arr[count1++][nums[i] % 2]++;
                nums[i] /= 2;
            }
        }
        int ans = 0;
        for(int i = 0;i < 32;++i)
            if(arr[i][1] % 2)
                ans += pow(2,i);
        if(t < 0)
            ans *= -1;
        return ans;
    }
};