目录
136. 只出现一次的数字
137. 只出现一次的数字 II
260. 只出现一次的数字 III
【题目】:
【代码】:
【题目】:
【代码】:
方法1:
java中存储一个int型整数,需要32位,我们也开32位的数组。以下为了表示方便只用4位。
假设有数组[5,1,5,1,5,1,4],写成二进制为:5:0110
1:0001
5:0110
1:0001
5:0110
1:0001
4:0100
T:0433 //每一列的和
R:0100 //模3
(T表示total,合计,每一列的和。R表示对3取模完之后的结果)
对T中的数值每一位取模3可以得到,出现了3的整数倍次的,取模完结果都是0;出现了非3的整数倍次的,即只出现了一次的那个数,取模完结果都为1,说明只出现一次的那个数,在当前这个位有出现过,最后也可以求出这个值。
但是时间复杂度好像不是线性时间复杂度~~~~~
效果:
方法2:我们想设计一个方法,使得一个数出现3次时能自动抵消为0,相当于模3,即
参考1:https://blog.csdn.net/pengchengliu/article/details/90437071
参考2:http://www.cnblogs.com/king-3/p/8763000.html
效果:
【题目】:
【代码】:
两个不相等的元素在位级表示上必定会有一位存在不同。
将数组的所有元素异或得到的结果ret为不存在重复的两个元素异或的结果。即例中的 5^3=6,(101^011=110)
bit=ret &( -ret)得到出 bit 最右侧第一个不为 0 的位,也就是只出现一次的两个元素在位级表示上最右侧不同的那一位,利用这一位就可以将所有元素分为两组,一组该位为1,另一组该位为0,对两个数组中的元素分别相与得到这两个不相同的数字。
【效果】: