LeetCode 136、137、260(只出现一次的数,异或性质及应用)

First. 陈列一下“异或”的一些性质

  异或是一种基于二进制的位运算,用符号XOR或者 ^ 表示,其运算法则是对运算符两侧数的每一个二进制位,同值取0,异值取1。

  它与布尔运算的区别在于,当运算符两侧均为1时,布尔运算的结果为1,异或运算的结果为0。

  性质

 

 

  1、交换律

 

  2、结合律(即(a^b)^c == a^(b^c))

 

  3、对于任何数x,都有x^x=0,x^0=x

 

  4、自反性 A ^ B ^ B = A ^  0 = A

   应用

 

  一、交换两个整数的值而不必用第三个参数
  a = 9;
  b = 11;

  a=a^b; 1001^1011=0010
  b=b^a; 1011^0010=1001
  a=a^b;  0010^1001=1011

  a = 11;
  b = 9;

  二、奇偶判断

  三、判断两个数是否相等  

  a ^ b == 0 ?

  四、格雷码(Gray code)

  五、奇数分频

Second. Leetcode136.只出现一次的数字

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

     说明:

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

     示例 1:          

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

     示例 2:

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

     代码解答如下:

/*给定一个非空整数数组
  除了某个元素只出现一次以外
  其余每个元素均出现两次
  找出那个只出现了一次的元素
*/
/*----------------------------------------头文件------------------------------------------------------*/
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
/*-------------------------------------使用异或的性质----------------------------------------------*/
class Solution1 {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 0; i < nums.size(); i++) {
            res ^= nums[i];  //使用异或的性质,相同为0,不同为1.    0^X=X   X^X=0
        }
        return res;
    }
};
/*-----------------------------------------使用哈希表-----------------------------------------------*/
class Solution2 {
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

 

Third. Leetcode136.只出现一次的数字Ⅱ

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

说明:

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

示例 1:

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

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

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

关于异或,或,非运算有以下性质:
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.

代码解答如下:

/*
给定一个非空整数数组,
除了某个元素只出现一次以外
其余每个元素均出现了三次
找出那个只出现了一次的元素
*/
#include <iostream>
#include <vector>
using namespace std;

class Solution2to1{
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;
    }
};

Forth. Leetcode136.只出现一次的数字Ⅲ

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

示例 :

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

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

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

根据异或的性质

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

巧妙之处:

假如A 1001   B 1101

A^B = 0010

刚开始flag=1;通过while循环和左移<<1可以得到一个值   0010

而0010和上面A  和  B  分别按位与   得到1和0,这样就可以分成两个数组

代码解答:

/*
给定一个整数数组 nums
其中恰好有两个元素只出现一次
其余所有元素均出现两次
找出只出现一次的那两个元素
*/
#include <iostream>
#include <vector>
using namespace std;

class Solution3to1 {
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 == 1) {
                result[0] ^= num;
            }
            else {
                result[1] ^= num;
            }
        }
        return result;
    }
};

 

 

 

有问题欢迎留言互相交流学习哈!!!!

上一篇:网络编程基本知识


下一篇:简单易写的九九乘法表 (C++代码)