Algorithm
题目概述：
Given an array of integers, every element appears three times except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
代码：
package 算法部分.数组; /** * 题目描述： * <p> * Given an array of integers, every element appears three times except for one. Find that single one. * <p> * Note: * Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? * * @author idea * @data 2019/6/29 */ public class Demo { public int singleNumber(int[] A) { for (int i = 0; i < A.length; i++) { int containCount = 0; for (int j = 0; j < A.length; j++) { if (A[i] == A[j]) { containCount++; } if (containCount == 2) { break; } } if (containCount == 1) { return A[i]; } } return -1; } public int singleNumber2(int[] A) { int a = 0 , b = 0; for(int c : A){ int ta,tb; ta = a; tb = b; a = (ta&(~tb)&(~c))|((~ta)&tb&c); b = ~ta&((~c&tb)|(~tb&c)); } return a|b; } public static void main(String[] args) { System.out.println(~1); Demo demo = new Demo(); int[] arr = {4, 11, 11, 11}; int result = demo.singleNumber2(arr); System.out.println(result); } } 复制代码
链接：www.nowcoder.com/questionTer…
来源：牛客网
写在前面：两个相同的数如果按位异或，最后结果就是0。如果三个数按位相异或（3,3,7），则三个数异或的结果就是7。以下的解法就是建立在这个思路上。异或使得两个相同的数的结果为0，我们要构造使得三个数异或的结果为0的运算。
分析：除了某一个数只出现了1 or 2次（出现次数%3==1 or 2），其余都出现了三次（或整数倍）。也就是说，如果有 模3加法（异或为模2加法），那么就很简单了，直接把所有数字按位相加。但二进制只有0、1，没有2，于是我们可以用两位a、b来表示三进制的两位，a为高位，b为低位。c表示数组A中的某一个数字的一位。则：
| 上一个a(ta) | 上一个b(tb) | 现在的c | 现在的a | 现在的b |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
注：因为是3进制，并没有a = 1,b = 1的两种情况，在卡诺图中可以随意包含或不包含
总结规律（利用卡诺图）可以得到 ：
a = (ta&(~tb)&(~c))|((~ta)&tb&c);
b = ~ta&((~c&tb)|(~tb&c));
得出最后的a、b后，需要得出结果r，a*2+b表示的就是r的某一位（每一位）叠加的次数(%3)，比如 a = 1, b = 0，表示r的某一位（每一位）出现了两次(%3) ，即那个单独的数出现了两次，则r的该位应该为1，因为叠加两次，数字就是原来大小的两倍。a = 0,b = 1同理。所以有如下结果：
| r | a | b |
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
注：a = 1 ,b= 1的情况不存在，卡诺图中可以包含也可以不包含。
这里不包含最简单，答案就是 r = a|b
