logo头像

学如逆水行舟,不进则退!!!

文章目录

位运算巧解独特数字筛查

一、题目描述

只出现一次的数字

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

示例1

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

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

二、思路分析

  • 咋看此题很是熟悉,这个和我们之前统计重复数字的题目如出一辙啊。而且当时我可以是通过四种方式来实现的。
  • hash解法、原地置换、跳位寻址等等。但是中间多多少少都引入了额外的变量
  • 在当时的原地置换中我们通过位运算进行两位数据交换。哪种解法还是很抢眼的。
  • 今天我们就是再次通过位运算来解决不重复的数据的。咋听起来可能有点迷茫。其实本题就是利用了位运算的原理充分解决的

异或运算

  • 首先我们得了解下位运算的计算规则。我们这里用到的位运算是异或运算

image-20210524190122111

  • 根据这个特性我们稍微整理下可以得出一个结论 : 0或者1和0进行异或得到的是其本身,进而我们能够得到任何数和0异或得到其本身

$$
x \wedge 0=x
$$

  • 相同为假,那么我们能够得出任何数和自己异或得到的是0

$$
x \wedge x=0
$$

  • 异或本身只和数字本身有关系,和数字异或的顺序没有关系,即先和a异或在和b异或与先和b异或在和a异或没有区别

$$
x \wedge a \wedge b= x \wedge b \wedge a
$$

回到本题

  • 基于上面三个定论,在结合我们题中的场景:只有一个数字是不重复的,其他数字都是成对出现的。
  • 因为异或没有顺序,那么不管怎么异或我们都可以改写成如下方式

$$
x \wedge a \wedge a \wedge b \wedge b \wedge c \wedge c ….. z \wedge z= x
$$

  • 所以我们只需要将数组中所有数据进行异或。最终的答案就是不重复的那个

三、AC 代码

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        result = result ^ nums[i];
    }
    return result;
}
  • 本题主要考察就是异或的使用。明白了位运算代码就不难实现了。

image-20210524191224306

四、总结

  • 位运算理解为计算机语言。善于利用位运算就是掌握了和计算机直接沟通的语言。
  • 有的时候会让我们的操作变成计算机级别的响应速度

多谢点个赞、关个注呀

上一篇
坚持原创技术分享,您的支持将鼓励我继续创作!

评论系统未开启,无法评论!