本文主要是介绍LintCode 落单的数 ⅡⅢ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
参考资料
落单的数Ⅱ
给出3*n + 1 个的数字，除其中一个数字之外其他每个数字均出现三次，找到这个数字。
样例
给出 [1,1,2,3,3,3,2,2,4,1] ，返回 4
落单的数Ⅲ
给出2*n + 2个的数字，除其中两个数字之外其他每个数字均出现两次，找到这两个数字。
样例
给出 [1,2,2,3,4,4,5,3]，返回 1和5
利用位运算操作。
Ⅱ ：
int类型有32位。对于每一个整数，转换为2进制，出现三次的数，每一位上的1也出现3次，那么把每一位上的1加起来对3取余，余数就是落单的数。
Ⅲ：
所有的数异或，结果就是两个落单的数A和B的异或结果，A⊕B（因为a⊕a=0；0⊕a=a）。设A⊕B=S。找到S的32位二进制位中为1的那一位，根据这一位将所有的数分成两组，那么每组就变成了落单的数Ⅰ。
代码如下：
Ⅱ ：
public class Solution {/*** @param A : An integer array* @return : An integer */public int singleNumberII(int[] A) {// write your code hereint[] bit=new int[32];int n=A.length;for (int i=0;i<n;i++){ //对每一个数for (int j=0;j<32;j++){ if(((1<<j)&A[i])!=0){ //1的二进制是0...0001(31个0)，利用1每次左移1位和//该数按位与运算，就能得到该位是0还是1.bit[31-j]=(bit[31-j]+1)%3;}}}int result=0;for (int i=0;i<32;i++){result=result*2+bit[i];//利用32位的二进制数求得十进制数。}return result;}
}Ⅲ：
public class Solution {/** @param A: An integer array* @return: An integer array*/public List<Integer> singleNumberIII(int[] A) {// write your code hereint n=A.length;int temp=0;for (int i=0;i<n;i++){//temp是所有数按位异或的结果temp=temp^A[i];}int temp1=0;for (int i=0;i<32;i++){//temp1是从低位开始找到的第一位是1的二进制位。if (((1<<i)&temp)!=0){temp1=i;break;}}//分组B和CVector<Integer> B=new Vector<Integer>();Vector<Integer> C=new Vector<Integer>();for (int i=0;i<n;i++){if(((1<<temp1)&A[i])!=0){B.add(A[i]);}else{C.add(A[i]);}} //每一组按照落单的数Ⅰ的方法计算List<Integer> result=new ArrayList();result.add(0);result.add(0);for (int i=0;i<B.size();i++){result.set(0,result.get(0)^B.get(i));}for (int i=0;i<C.size();i++){result.set(1,result.get(1)^C.get(i));}return result;}
}这篇关于LintCode 落单的数 ⅡⅢ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
