数组中只出现一次的数字II

题目描述

一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

分析

本题是有两个未知数,是”Single Number”这道题的扩展,直接做异或肯定是不行的。有没有办法把两个未知数分开,使得可以分别应用Single Number的解法呢?
设x,y是那两个未知数,那么如果对这个数组做异或的话,结果实质上等于x^y,因为其他数都出现了两次,被抵消了。
但是仅仅是通过最后异或出来的值,是没办法区分出x和y的,但是足以帮助我们把 x和y划分到不同的子数组中去。

代码:

//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class Solution {
public void FindNumsAppearOnce(int[] array,int num1[] , int num2[]) {
int xorresult = 0;
int flag = 1;
for (Integer i : array){
xorresult ^= i;
}
while ((xorresult & flag) == 0)
flag <<= 1; //找出x和y第一个不同的二进制位
for (Integer i : array){ //把x和y划分到不同的子数组中,然后分别用异或。
if ((i & flag) == 0)
num2[0] ^= i;
else
num1[0] ^= i;
}
}
}

欢迎关注公众号: FullStackPlan 获取更多干货

Copyright © 2016 - 2017 LBD All Rights Reserved.

访客数 : | 访问量 :