孤单数算法

1.背景

腾讯终面：孤单的QQ号码怎么找？

问题一：有n个QQ号码，除1个孤单的QQ号码外，其余的QQ号码都是成双成对的，求这个孤单的QQ号码，要求：时间复杂度为O(n), 空间复杂度为O(1).

问题二：有n个QQ号码，除2个孤单的QQ号码外，其余的QQ号码都是成双成对的，求这2个孤单的QQ号码，要求：时间复杂度为O(n), 空间复杂度为O(1).

问题一求解方案：

方法一：所有数据放在数组中，下标标识qq号，值等于出现次数，然后遍历。

方法二：所有数字相减

方法三：异或方案

问题二求解方案：

基于问题方法三的思路，出现一对的的数字二进制编码是相同的，两个孤单数可以分成两组，数字转换成二进制之后，最后一位根据0 和1 分组，然后分别异或得到两个不同的值。

2.异或java实现

package test;import java.util.ArrayList;public class AloneNums {public static void main(String[] args) {aloneNums();aloneNums2();}// 一个孤单数static void aloneNums(){int[] a ={520, 216, 216, 520, 111};int  res=0;//System.out.println(a);for(int i : a) {res^=i;}System.out.println(res);}// 两个孤单数static void aloneNums2(){int[] a ={520, 216, 216, 520, 111,734};class Tmp {int a;String astr;void seta(int a ){ this.a = a;}void setastr(String astr ){ this.astr = astr;}};ArrayList<Tmp> res = new ArrayList<>();int alone1=0,alone2=0 ;for(int i : a) {String binaryNum = Integer.toBinaryString(i);Tmp t = new Tmp();t.seta(i);t.setastr(binaryNum);res.add(t);}for(Tmp i : res) {String str = i.astr;// 字符串最后一位  str.substring(str.length()-1)// 1 和 0 分类,然后分别异或if(str.substring(str.length()-1).equals("1")){alone1^=i.a;}elsealone2^=i.a;}System.out.println(alone1);System.out.println(alone2);}
}

3.遗留问题

    n个孤单数如何寻找？