LeetCode | 136. 只出现一次的数字Ⅰ Ⅱ

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]

输出: 1

示例 2:

输入: [4,1,2,1,2]

输出: 4

挺简单的，因为楼主之前就常用位运算符就很快解出来了

使用无序map（比map明显加快很多100ms->40ms）

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        unordered_map<int,int>m;

        for(int i=0;i<nums.size();++i){

            if(m.find(nums[i]) != m.end()){

                m.erase(m.find(nums[i]));

            }else{

                m[nums[i]] = 1;

            }

        }

        return m.begin()->first;

    }

};

^运算符

^运算符的运算符合（类似）乘法交换律

即 1^ 2 ^ 3 ^ 2 ^ 3 = 1 ^ 2 ^ 2 ^ 3 ^3 = 1

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int a=nums[0];

        for(int i=1;i<nums.size();i++)

            a=a^nums[i];

        return a;

    }

};

更多位运算符的骚操作可以看我另一篇博文传送门

进阶：

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]

输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]

输出: 99

考虑到要查找存在3个，所以我们直接利用两个变量存储

class Solution {

public:

    int singleNumber(vector<int>& nums) {

        int a = 0, b = 0;

        for (auto x : nums) {

            b = (b ^ x) & ~a;

            a = (a ^ x) & ~b;

        }

        return b;

    }

};

巴特西

LeetCode | 136. 只出现一次的数字Ⅰ Ⅱ

最新文章

热门文章