Skip to content

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;
    }
};


回到顶部