01 PART
Single Number
这道题,大家先想一想是用什么思路进行求解?
第136题:给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
PS:建议大家停留个两分钟先想一想...直接拉下去看题解就没什么意思了。
02 PART
题目分析
位运算的题目我们已经讲了好几道了,这道也不例外,也是其中一个非常典型的例子!属于必须掌握的题型。
直接分析,我们要找只出现一次的数字,并且已知了其他的数字都只出现了两次。那么这种一听其实就应该想到需使用位运算来进行求解。最好的,就是在读完题目的瞬间,直接条件反射!(当然,如果你现在第一反应是想到 通过遍历统计,或者其他如使用hashmap 等方式来进行求解,那我觉得你的位运算这块,是有必要加强练习力度的。如果你第一反应,连思路都没有,那我觉得对于整个算法的能力这块,都是比较欠缺的,需要下苦功!)
回到题目,如何使用位运算进行求解呢?对于任意两个数a和b,我们对其使用 “异或”操作,应该有以下性质:
a⊕b⊕a=(a⊕a)⊕b=0⊕b=b
可能有人直接都不知道异或是什么,所以还是举个例子,比如5异或3,也就是5⊕3,也就是5^3,是下面这样:
根据分析,得出代码:(c++版本)
//CPP
class Solution {
public:
int singleNumber(vector<int>& nums) {
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
};
(java版本)
//JAVA
class Solution {
public int singleNumber(int[] nums) {
int ans = nums[0];
for (int i = 1; i < nums.length; i++) {
ans = ans ^ nums[i];
}
return ans;
}
}
(python版本)
//py
class Solution:
def singleNumber(self, nums: List[int]) -> int:
ans = 0
for i in range(len(nums)):
ans ^= nums[i]
return ans
郑重申明(读我的文章必看):
03 PART
题目进阶
如果修改上面的题目,除了某个元素只出现一次,其余元素都出现了3次以上,那么该如何求解?
修改一个条件之后,本题的难度大幅度提升!“异或”的方式看起来似乎没办法运用在“其余数出现3次以上”的条件中。那对于这种问题又该如何求解?我这里给出几种思路,大家下去分析一下,明天我会公布这道衍化题型的解决方案: