|
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
示例 1: 输入: [2,2,3,2]
输出: 3 示例 2: 输入: [0,1,0,1,0,1,99]
输出: 99 答案： 1public int singleNumber(int[] nums) {
2 int a = 0, b = 0;
3 for (int i = 0; i < nums.length; ++i) {
4 b = (b ^ nums[i]) & ~a;
5 a = (a ^ nums[i]) & ~b;
6 }
7 return b;
8}
解析：
有没有能看得懂的，是不是一脸懵逼，如果一眼能看懂的我觉得也算是高手了。如果看不懂我就继续让你懵逼
1public int singleNumber(int[] nums) {
2 int x1 = 0, x2 = 0, mask = 0;
3 for (int i : nums) {
4 x2 ^= x1 & i;
5 x1 ^= i;
6 mask = ~(x1 & x2);
7 x2 &= mask;
8 x1 &= mask;
9 }
10 return x1;
11}
what，还看不懂，那我再给你写一个
1public int singleNumber(int[] nums) {
2 int a = 0;
3 int b = 0;
4 for (int c : nums) {
5 int ta = (~a & b & c) | (a & ~b & ~c);
6 b = (~a & ~b & c) | (~a & b & ~c);
7 a = ta;
8 }
9 return a | b;
10}
看不懂没关系，我们最后再讲，现在我先给大家介绍两个能看懂的，增强一下信心。一种是使用HashMap来存储，key存储数组的值，value存储的是key值出现的次数，最后找出value等于1的即可。原理很简单，代码就不再写了。还一种方式是使用位来存储，我们来先看下代码 1public int singleNumber(int[] nums) {
2 int ans = 0;
3 for (int i = 0; i < 32; i++) {
4 int sum = 0;
5 for (int j = 0; j < nums.length; j++) {
6 if (((nums[j] >> i) & 1) == 1) {
7 sum++;
8 sum %= 3;
9 }
10 }
11 if (sum != 0) {
12 ans |= sum << i;
13 }
14 }
15 return ans;
16}
或者 1public int singleNumber(int[] nums) {
2 int bitLength = 32;
3 int bits[] = new int[bitLength];
4 for (int i = 0; i < bitLength; i++) {
5 for (int j = 0; j < nums.length; j++) {
6 bits[i] += ((nums[j] >> i) & 1);
7 }
8 }
9 int result = 0;
10 for (int j = 0; j < bitLength; j++)
11 if (bits[j] % 3 != 0)
12 result += (1 << j);
13 return result;
14}
这种代码很容易理解，因为int是32位，所以只需要累加每一位上的和，看他是否能被3整除，如果不能整除，说明那个只出现一次的数字在这个位置上是有值的。举个例子，假如数组[5,5,5,6]那么他们的二进制分别是
101
101
101 110 ——
所以相加的结果第一位是（从左往右）1+1+1+1=4，不能被3整除，所以结果为1，第二位0+0+0+1也不能被3整除，所以结果也为1，第三位1+1+1+0=3能被3整除，所以结果为0，所以我们要查找的那个数的二进制是110，换成十进制也就是6。代码很容易理解， 下面再看最重要的部分，也就是上面遗留的问题，最上面3种解法的原理是什么。其实他的原理非常简单，就是一个数如果出现3次，通过一些运算我们让他变为0，也就是说他的周期是3，前面我们讲过140，只出现一次的数字，通过异或运算即可。这种想法很容易想到，但怎么让他出现3次的时候让他变为0，就不那么简单了。
比如一个数x第一次出现的时候让他保存在b中，第二次出现的时候让他保存在a中，第3次出现的时候让他等于0，所以对于第一种解法我们很容易写出b=(b^x)&~a; a=(a^x)&~b;
对于第3种解法。我们看到3个相同的数每次执行完之后都会归0，也就是说他的周期是3，只要一个数出现3次就让他归0。那么他是怎么实现的呢，其实也很好理解，因为他的周期是3，那么他就具有3种状态。我们就拿0和1来说，如果用0和1来表示3种状态我们至少需要2位数，我们假如这3种状态是00，01，10。这里的3个数我们把它理解为三种状态，不要把它当成一个数，每次都会在这3种状态中循环，当出现3次的时候就让他回到初始状态。我们看一下 /** * * 3种状态 * 存储 输入 结果 * ab c ab * 00 1 01 * 01 1 10 * 10 1 00 * * 00 0 00 * 01 0 01 * 10 0 10 * * 所以可以列出下面公式 * a=a&~b&~c | ~a&b&c * b= ~a&b&~c|~a&~b&c */ 我们上面刚才说了，ab只是表示一种状态，那么假如我不选择ab为00，01，10这3种状态，我们选择ab为00，01，11三种状态可不可以，其实完全可以，不管怎么选只要我们保证他的周期是3就行，我们来分析一下如果选00，01，11这3种状态下是什么样的一种情况。
/** * * 3种状态 * 存储 输入 结果 * ab c ab * 00 1 01 * 01 1 11 * 11 1 00 * * 00 0 00 * 01 0 01 * 11 0 11 * * 所以可以列出下面公式 * a=a&~b&~c | ~a&b&c|a&b&~c * b= ~a&b&~c|~a&~b&c|~a&b&c|a&b&~c */ 1public int singleNumber(int[] nums) {
2 int a = 0, b = 0, i = 0, length = nums.length;
3 while (i < length) {
4 int c = nums[i];
5 int ta = a & ~b & ~c | ~a & b & c | a & b & ~c;
6 b = ~a & b & ~c | ~a & ~b & c | ~a & b & c | a & b & ~c;
7 a = ta;
8 i++;
9 }
10 return b;
11}
写法上确实要复杂一点。确实有一定的难度，希望大家能收藏下来，或者发送给喜欢算法的同学一起来研究下。这里面有很多精髓的地方，并且写法也非常多，我没有一一列出，大家有兴趣的可以研究下。 这里顺便再出几道题， 1，从数组中找出只出现一次的两个数，数组中其他数都出现两次。（就是有2个数只出现一次，其他的数都出现了两次） 1private static int[] findTwo(int[] array) {
2 if (array.length <= 2)
3 return array;
4 int res = 0;
5 for (int i = 0; i < array.length; i++) {
6 //计算只出现一次的两个数^的结果
7 res ^= array[i];
8 }
9 int index = 1;//从右往左找出第一次出现1的位置。
10 while (res != 0) {
11 if ((res & 1) == 0) {
12 res = res >> 1;
13 index = index << 1;
14 } else {
15 break;
16 }
17 }
18 /**
19 *index实际上是从0开始的，但初始化为1，因为如果初始化为0，
20 *无论怎么移还是0，所以相当于往左多移了一步，这里再往右移一步
21 */
22 index = index >>> 1;
23 int[] result = new int[2];
24 for (int i = 0; i < array.length; i++) {
25 if (((array[i] >> index) & 1) == 1)
26 result[0] ^= array[i];
27 else
28 result[1] ^= array[i];
29 }
30 return result;
31}
我只把结果写上，具体逻辑大家自己去分析
2，从数组中找出只出现一次的三个数，数组中其他数都出现两次。（就是有3个数只出现一次，其他的数都出现了两次） 1private static int[] findThree(int[] array) {
2 return findThree(array, 1);
3}
4
5private static int[] findThree(int[] array, int index) {
6 int lastOneBit = index;
7 if (array.length <= 3)
8 return array;
9 int res = 0;
10 for (int i = 0; i < array.length; i++) {
11 //计算只出现一次的三个数^的结果
12 res ^= array[i];
13 }
14 while (res != 0) {
15 if ((res & 1) == 0) {
16 res = res >> 1;
17 lastOneBit = lastOneBit << 1;
18 } else {
19 break;
20 }
21 }
22 /**
23 * 如果第一次调用当res为0的时候，就表示res的二进制位中是没有1的，
24 * 那么这样再根据res上是否为1来判断就没有意义了，所以如果出现这种
25 * 情况他是根据最右边的0或1来划分的，如果不幸又分到一组了，那么继
26 * 续递归调用，同时++index，从最右边第二位开始，以此类推，直到这
27 * 3个数没有分到同一组为止。
28 */
29 /**
30 *这里lastOneBit往右移一位的原因是，应该是从最右边第一位开始判断的，
31 * index应该是0，但在第一次调用的时候传的是1，所以这里要往右移一位，
32 * 第一次调用的时候能不能传0，这个是不行的，因为在执行上面的while循环
33 * 的时候0无论往左移多少位都还是0，所以不能传0。
34 */
35 lastOneBit = lastOneBit >>> 1;
36 int[] result = new int[3];
37 List part1 = new ArrayList();//根据0和1分为两部分
38 List part2 = new ArrayList();
39 for (int i = 0; i < array.length; i++) {
40 if (((array[i] >> lastOneBit) & 1) == 1) {
41 part1.add(array[i]);
42 result[0] ^= array[i];
43 } else {
44 part2.add(array[i]);
45 result[1] ^= array[i];
46 }
47 }
48 /**
49 * 下面分4种情况讨论,当然0和1的顺序可以打乱
50 * 1,1^1^1==1
51 * 2,0^0^0==0
52 * 3,0^1^1==0
53 * 4,0^0^1==1
54 */
55 int[] temp;
56 if ((part1.size() & 1) == 1) { //有奇数个数，是上面的1,4
57 if (result[1] == 0) {//情况1
58 return findThree(listToArray(part1), ++index);
59 } else {//情况4
60 temp = findTwo(listToArray(part2));
61 }
62
63 } else {//有偶数个数，是上面的2,3
64 if (result[0] == 0) {//情况2
65 return findThree(listToArray(part2), ++index);
66 } else {//情况3
67 temp = findTwo(listToArray(part1));
68 }
69
70 }
71 result[1] = temp[0];
72 result[2] = temp[1];
73 return result;
74}
75
76private static int[] listToArray(List<Integer> mList) {
77 int[] array = new int[mList.size()];
78 for (int i = 0; i < mList.size(); i++) {
79 array[i] = mList.get(i);
80 }
81 return array;
82}
上面代码都有注释，我就不再分析。下面在分析一种解法
这三个数中只要我们找到一个，其他两个就迎刃而解了，我们换个思路再来分析一下，假如这三个数是a，b，c，他们异或的结果为x，则x=a^b^c；进一步我们可以推算出a^x=b^c，b^x=a^c，c^x=a^b；我们令A=a^x，B=b^x，C=c^x，因为a，b，c都各不相同，所以A，B，C都不为0，我们令f（x）表示x从右边数遇到的第一个1不变，其他的全部置为0的值，比如f（6）=f（0110）=0010=2，f（11）=f（1011）=0001=1。我们令g=f（A）^f（B）^f（C）；我们进一步可以得出g肯定是不为0的，因为A，B，C都不为0，所以f（A），f（B），f（C）也分别都不为0，所以他们二进制位有且仅有一个1，其他都是0，也可以说f（A），f（B），f（C）都是2的n次方。假如f（A）^f（B）等于0，那么0^f（C）肯定不等于0，因为f（C）不等于0，所以g不等于0。假如f（A）^f（B）不等于0，那么他们异或结果的二进制位肯定有两个1，然后再与f（C）异或结果肯定不为0，所以可以肯定的是g不为0。我们还可以进一步得出结论g转化为二进制的时候至少有1个1，至多3个1。我们假设g的二进制位从右边数第m位是1，那么f（A），f（B），f（C）从右边数第m位要么只有一个是1其他两个是0，要么3个都是1。假如3个都是1，那么我们可知x的第m位和a，b，c的第m位相反。假如x的第m位是1，那么a，b，c的第m位都为0，所以a^b^c运算结果的第m位不可能为1，所以不成立。假如x的第m位是0，那么a，b，c的第m位都为1，所以a^b^c运算结果的第m位不可能为0，所以可以得出结论f（A），f（B），f（C）的第m位不可能都是1，只能是一个为1，其他两个为0。所以我们的解决方式就有了，把所有值都异或一遍就得到x，x再与a，b，c分别异或求出A，B，C，然后在求出f（A），f（B），f（C）的值，最后在求出g，后面的就很简单了。 1private static int[] findThree2(int[] array) {
2 int length = array.length;
3 int result[] = new int[3];
4 int temp[] = new int[length + 1];
5 int xorResult = 0;//所有数值异或的结果
6 int i, lastbit1 = 0;
7 for (i = 0; i < length; i++) {
8 //xorResult就是上面分析的x=a^b^c
9 xorResult ^= array[i];
10 temp[i] = array[i];
11 }
12 for (i = 0; i < length; i++) {
13 //lastbit1相当于上面分析的g=f（A）^f（B）^f（C）,
14 // xorResult ^ array[i]相当于A，B，C
15 lastbit1 ^= lastBitOf1(xorResult ^ array[i]);
16 }
17 //上面分析的g从右边数第m为是1，其他置为0，因为上面分析的f（A），f（B）
18 // ，f（C）的第m位只有一个是1，其他两个是0，
19 lastbit1 = lastBitOf1(lastbit1);
20
21 for (i = 0; i < length; i++) {
22 // array[i] ^ xorResult相当于A，B，C，在f（A），f（B）f（C）中
23 //第m位为1的分为一组，进行异或运算求得值
24 if (lastBitOf1(array[i] ^ xorResult) == lastbit1)
25 result[0] ^= array[i];//找到第一个值
26 }
27 //第一个值找到后放到数组中让他的个数成为偶数，问题转化为求剩余两个的值
28 temp[length] = result[0];
29 //让xorResult成为剩余两个数异或的结果
30 xorResult ^= result[0];
31 //两个数的时候就可以根据右边第一次出现两个不同的值1和0的时候来划分。
32 lastbit1 = lastBitOf1(xorResult);
33 for (i = 0; i < length + 1; i++) {
34 if ((temp[i] & lastbit1) != 0)
35 result[1] ^= temp[i];//找到第二个值
36 }
37 result[2] = xorResult ^ result[1];//找出第三个
38 return result;
39}
40
41private static int lastBitOf1(int num) {
42 return num & (-num);
43}
3，从数组中找出只出现m次数，数组中其他数都出现n次（使用&运算符解答，并且m不等于n，也不能是n的倍数）
当然这种解法就比较多了，因为m和n都不确定，我们也没有一个万能的公式，我们需要根据具体的m和n来实现不同的算法，我们假如n等于4，有4个重复的，看下怎么写 /** * * 4种状态 * 存储 输入 结果 * ab c ab * 00 1 01 * 01 1 10 * 10 1 11 * 11 1 00 * * 00 0 00 * 01 0 01 * 10 0 10 * 11 0 11 * * 所以可以列出下面公式 * a=~a&b&c|a&~b&c|a&~b&~c|a&b&~c * b= ~a&~b&c|a&~b&c|~a&b&~c|a&b&~c */ 1public static int findOnce4(int[] array) {
2 int a = 0, b = 0, i = 0, length = array.length;
3 while (i < length) {
4 int c = array[i];
5 int ta = ~a & b & c | a & ~b & c | a & ~b & ~c | a & b & ~c;
6 b = ~a & ~b & c | a & ~b & c | ~a & b & ~c | a & b & ~c;
7 a = ta;
8 i++;
9 }
10 return a | b;
11}
下面的几个只是列出了答案，具体问题大家可以自己分析。如果能研究透，基本上对二进制有关的算法会有一个很大的提升。也希望大家多看多想多练，思考非常重要。当然后面的推送可能要暂停一段时间，真的是希望大家能把这块研究透，如果实在不感兴趣在这段时间可以看看以前的题
|
