136、137、260 只出现一次的数字
|
一、136 数组中其他数都出现了2次，只有一个数出现了一次，把这个数找出来 点击此处返回总目录 二、137 数组中其他数都出现了3次，只有一个数出现了一次，把这个数找出来 三、260 数组中其他数都出现了2次，只有两个数各出现了一次，把这两个数找出来
一、数组中其他数都出现了两次，只有一个数出现了一次，把这个数找出来
【题目】
【分析】 异或运算。不同为1，相同为0。所以2个相同的数异或得到一串0。 0与1异或得1，0与0异或得0。所以0与一个数异或得到这个数本身。 因此：把所有的数异或得到的就是这个数。
【代码】
【运行结果】
二、数组中其他数都出现了三次，只有一个数出现了一次，把这个数找出来
【题目】
【分析】 位运算。 我们知道当数字x出现一次时，通过 x^0 可以记录下这个数x。 当数字出现两次时，再通过x^x，就可以把这个数擦掉。 因此，设置int a =[0][0][0][0][0][0][0][0]，每个[0]代表一位。当x[i]出现偶数次时，a[i]^x[i] = 0。当x[i]出现奇数次时，a[i]^x[i]=x[i]。
现在我们希望当数字出现一次时，记下来。当数字出现2次时，记下来。当数字出现3次时，置0。 我们使用两个变量a和b做记录。 int b=[0][0][0][0][0][0][0][0]; int a=[0][0][0][0][0][0][0][0];
我们需要： 当x[i]出现1次时，b[i]=[0]，a[i]=x[i] 当x[i]出现2次时，b[i]=x[i]，a[i]=0 当x[i]出现3次时，b[i]=0，a[i]=0
0 1 2 3 4 5 6 b[i]: 0 -> 0 -> 1 -> 0 ->0 -> 1 -> 0 a[i]: 0 -> 1 -> 0 -> 0 -> 1 -> 0 -> 0
我们来看一下设计的逻辑： a = (a^ num) & ~b b = (b^ num) & ~a
至于为什么这么设计，估计要回去复习一下逻辑电路那本书了。我们手动模拟一遍。 初始： b[i]=0 a[i]=0 当第一次出现1： a^1 = 1 , ~b = 1，1&1 = 1，所以a[i] = 1。b^1 = 1,~a = 0 , 1&0 = 0 ,所以b[i]=0。 正确。 当第二次出现1： a^1 = 1^1 = 0 , ~b = 1，0&1 = 0，所以a[i]= 0。b^1 = 1，~a=1,1&1 = 1，所以b[i]=1。正确。 当第三次出现1： a^1 = 0^1 = 1，~b = 0, 1&0 = 0，所以a[i] = 0。b^1 = 0，~a = 1, 0&1 = 0，所以b[i]=0。正确。
初始：b[i]=0 a[i]=0 当第一次出现0： a^0 = 0 , ~b = 1，0&1 = 0，所以a[i] = 0。b^0 = 0,~a = 1 , 0&1 = 0 ,所以b[i]=0。 当第二次出现0： a^0 = 0^0 = 0，~b = 1，0&1 = 0，所以a[i] = 0。b^0 = 0，~a = 1，0&1 = 0，所以b[i]=0。 当第三次出现0： a^0 = 0^0 = 0，~b = 1，0&1 = 0，所以a[i] = 0。b^0 = 0，~a = 1，0&1 = 0，所以b[i]=0。 当出现0时，不改变a[i],b[i]的值。
【代码】
【结果】
三、数组中其他数都出现了2次，只有两个数各出现了一次，把这两个数找出来 【题目】
【分析】 比如有以下数字： 2： 0 0 0 0 0 0 1 0 4： 0 0 0 0 0 1 0 0 3： 0 0 0 0 0 0 1 1 3： 0 0 0 0 0 0 1 1 6： 0 0 0 0 0 1 1 0 6： 0 0 0 0 0 1 1 0
首先全部异或得到一个数，该数就是3和4异或的结果。 a： 0 0 0 0 0 1 1 0 分析这个数会发现，a中为0的位，说明原来的两个数这一位相同。a中为1的位，说明两个数这一位不同。 这样我们就可以根据这一位将所有的数分成两堆，每一堆的结构如下：其他数都出现了两次，只有一个数出现了一次，找出这个数。这就变成了第一题。 比如，根据倒数第2位将数划分为： （2,3,3,6,6）（4） 根据倒数第3位将数划分为： （2,3,3）(4,6,6)
【代码】
【结果】
红线划掉是因为，这是其他题目的提交记录。LeetCode不知道是不是有bug。
|