前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >位运算问题-LeetCode 136、137、260(只出现一次的数,异或运算)

位运算问题-LeetCode 136、137、260(只出现一次的数,异或运算)

作者头像
算法工程师之路
发布2019-11-04 02:30:47
6130
发布2019-11-04 02:30:47
举报
文章被收录于专栏:算法工程师之路

【LeetCode #136】只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。 说明: 你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗?

示例 1:

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

解题思路:

异或的性质: 其基本性质为,相同为1,不同为0. 满足交换律,结合律,分配律,并且还有三个很重要的应用方面。

  • 自反性质:a ^ b ^ b = a ^ 0 = a
  • 交换两个数:a = a ^ b; b = a ^ b; a = a ^ b;
  • 判断两个数是否相等:a ^ b == 0
代码语言:javascript
复制
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(int i = 0; i < nums.size(); i++){
            res ^= nums[i];
        }
        return res;
    }
};

使用hashmap将每个数字对应的个数存入哈希表中,然后遍历整个数组进行检查!

代码语言:javascript
复制
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int, int> mm;
        for(auto n : nums){
            if(mm.count(n)){
                mm[n]++;
            }else{
                mm.emplace(n, 1);
            }
        }
        for(auto n : nums){
            if(mm[n] == 1){
                return n;
            }
        }
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/single-number

【LeetCode #137】只出现一次的数字 II

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

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

示例 1:

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

解题思路:

关于异或,或,非运算有以下性质: 0 ^ x = x, x ^ x = 0, x & ~x = 0, x & ~0 = x.

  1. x第一个出现后,经过下面的程序可以得到 a = x, b = 0;
  2. x第二次出现后,经过下面的程序可以得到 a = 0, b = x;
  3. x第三次出现后,经过下面的程序可以得到 a = 0, b = 0;

而只出现一次的数字,经过程序得到a = x, b = 0; 所以最后函数返回值为a.

代码语言:javascript
复制
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for(auto num: nums){
            a = (a ^ num) & ~b;
            b = (b ^ num) & ~a;
        }
        return a;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/single-number-ii

【LeetCode #260】只出现一次的数字 III

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。 示例 :

输入: [1,2,1,3,2,5] 输出: [3,5]

注意: 结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

解题思路:

根据异或的性质,如果数组中只有两个数出现次数为1,分别为A和B,其他出现次数为2,那么首先第一步直接对所有数据进行异或,最终会得到A^B的结果! 接着寻找A^B位数为1的地方,通过flag << 1得到,这样就可以将整个数组分成两个部分,第一部含有所有num&flag = 1的数,另一部分含有所有num&flag = 0的数。 最后分别对这两部分使用异或既可了,参考于LeetCode #136

代码语言:javascript
复制
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto num: nums){
            res ^= num;
        }
        int flag = 1;
        while((res & flag) == 0)
            flag = flag << 1;
        vector<int> result(2, 0);
        for(auto num: nums){
            if(num & flag){
                result[0] ^= num;
            }else{
                result[1] ^= num;
            }
        }
        return result;
    }
};

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/single-number-iii

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-10-31,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 算法工程师之路 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 【LeetCode #136】只出现一次的数字
  • 【LeetCode #137】只出现一次的数字 II
  • 【LeetCode #260】只出现一次的数字 III
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档