漫画：位运算系列篇（只出现一次的数字）

今天是小浩算法“365刷题计划”第62天。仍然分享一道关于位运算颇为简单的题型&＃xff0c;同时&＃xff0c;从明天开始将会提高难度&＃xff0c;大家做好准备。

01

PART

Single Number

这道题&＃xff0c;大家先想一想是用什么思路进行求解&＃xff1f;

第136题&＃xff1a;给定一个非空整数数组&＃xff0c;除了某个元素只出现一次以外&＃xff0c;其余每个元素均出现两次。找出那个只出现了一次的元素。

&＃xff08;瞪一瞪就全部掌握&＃xff09;

PS&＃xff1a;建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。

02

PART

题目分析

位运算的题目我们已经讲了好几道了&＃xff0c;这道也不例外&＃xff0c;也是其中一个非常典型的例子&＃xff01;属于必须掌握的题型。

直接分析&＃xff0c;我们要找只出现一次的数字&＃xff0c;并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的&＃xff0c;就是在读完题目的瞬间&＃xff0c;直接条件反射&＃xff01;&＃xff08;当然&＃xff0c;如果你现在第一反应是想到 通过遍历统计&＃xff0c;或者其他如使用hashmap 等方式来进行求解&＃xff0c;那我觉得你的位运算这块&＃xff0c;是有必要加强练习力度的。如果你第一反应&＃xff0c;连思路都没有&＃xff0c;那我觉得对于整个算法的能力这块&＃xff0c;都是比较欠缺的&＃xff0c;需要下苦功&＃xff01;&＃xff09;

回到题目&＃xff0c;如何使用位运算进行求解呢&＃xff1f;对于任意两个数a和b&＃xff0c;我们对其使用 “异或”操作&＃xff0c;应该有以下性质&＃xff1a;

• 任意一个数和0异或仍然为自己&＃xff1a;

  a⊕0&＃61;a

• 任意一个数和自己异或是0&＃xff1a;

  a⊕a&＃61;0
  

• 异或操作满足交换律和结合律&＃xff1a;

a⊕b⊕a&＃61;(a⊕a)⊕b&＃61;0⊕b&＃61;b

可能有人直接都不知道异或是什么&＃xff0c;所以还是举个例子&＃xff0c;比如5异或3&＃xff0c;也就是5⊕3&＃xff0c;也就是5^3&＃xff0c;是下面这样&＃xff1a;

根据分析&＃xff0c;得出代码&＃xff1a;&＃xff08;c&＃43;&＃43;版本&＃xff09;

1//CPP2class Solution {3public:4    int singleNumber(vector& nums) {5        int ans &＃61; 0;6        for (int num : nums) {7            ans ^&＃61; num;8        }9        return ans;
10    }
11};


&＃xff08;java版本&＃xff09;

1//JAVA2class Solution {3    public int singleNumber(int[] nums) {4        int ans &＃61; nums[0];5        for (int i &＃61; 1; i < nums.length; i&＃43;&＃43;) {6            ans &＃61; ans ^ nums[i];7        }8        return ans;9    }
10}


(python版本)

1//py
2class Solution:
3    def singleNumber(self, nums: List[int]) -> int:
4        ans &＃61; 0
5        for i in range(len(nums)):
6            ans ^&＃61; nums[i]
7        return ans


郑重申明&＃xff08;读我的文章必看&＃xff09;&＃xff1a;

• 本系列所有教程都不会用到复杂的语言特性&＃xff0c;不需要担心没有学过相关语法&＃xff0c;使用各语言纯属本人爱好。

• 作为学术文章&＃xff0c;虽然风格可以风趣&＃xff0c;但严谨&＃xff0c;我是认真的。本文所有代码均在leetcode上进行过测试运行。

• 算法思想才是最重要的。

03

PART

题目进阶

如果修改上面的题目&＃xff0c;除了某个元素只出现一次&＃xff0c;其余元素都出现了3次以上&＃xff0c;那么该如何求解&＃xff1f;

修改一个条件之后&＃xff0c;本题的难度大幅度提升&＃xff01;“异或”的方式看起来似乎没办法运用在“其余数出现3次以上”的条件中。那对于这种问题又该如何求解&＃xff1f;我这里给出几种思路&＃xff0c;大家下去分析一下&＃xff0c;明天我会公布这道衍化题型的解决方案&＃xff1a;

• 思路1&＃xff1a;使用hashmap&＃xff0c;统计每个数字出现的次数&＃xff0c;最后返回次数为1的数字。。。然后等待一段时间&＃xff0c;接到很遗憾的通知。

• 思路2&＃xff1a;上面的题目&＃xff0c;对于相同的两个数&＃xff0c;进行异或运算&＃xff0c;我们可以进行“抵消”&＃xff0c;那是否可以找到一种方式&＃xff0c;来让相同的三个数进行相互抵消呢&＃xff1f;

• 思路3&＃xff1a;是不是可以通过数学的方式来进行计算&＃xff1f;

&＃xff08;这货就是不直接说出来&＃xff0c;你说气人不气人&＃xff01;&＃xff09;

想复习一下其他位运算题目的&＃xff0c;可以看&＃xff1a;

漫画&＃xff1a;三分钟学习一道位运算的面试题&＃xff0c;万一遇到了呢&＃xff1f;

漫画&＃xff1a;位运算技巧助你俘获offer

所以&＃xff0c;今天的问题你学会了吗&＃xff1f;评论区留下你的想法&＃xff01;

1. 全栈架构之打包推荐【建议收藏&＃xff0c;常读】

2. 一个空格引发的“惨案“

3. 分布式系统中Session共享的常用方案

4. Java语言“坑爹”排行榜TOP 10

5. 我是一个Java类&＃xff08;附带精彩吐槽&＃xff09;

6. mysql索引失效&＃xff0c;差点我的工作凉了

7. 既生synchronized&＃xff0c;何生volatile&＃xff1f;

8. 微服务一直火&＃xff0c;为什么服务化要搞懂&＃xff1f;

9. MySQL的COUNT语句&＃xff0c;不简单&＃xff01;

10. 漫画&＃xff1a;HashSet和TreeSet实现与原理

扫码二维码关注我

·end·

—如果本文有帮助&＃xff0c;请分享到朋友圈吧—

我们一起愉快的玩耍&＃xff01;

你点的每个赞&＃xff0c;我都认真当成了喜欢