题目描述：
给一个整型数组，除了一个整数只出现一次，其他所有整数均出现两次，找出给唯一出现一次的数分析：
位运算，利用位运算的性质做题，出现过两次基本上代表了异或结果为0，数组所有元素异或最终结果就是目标元素
public class Solution {
public int singleNumber(int[] nums) {
int i = nums[0];
for(int k = 1; k < nums.length;k++)
{
i ^= nums[k];
}
return i;
}
}
- 扩展
- Single Number II：除一个元素出现一次之外，其他元素均出现三次，求该唯一元素
- Single Number III：除两个元素出现一次之外，其他元素均出现过两次，求这两个元素
// Single Number II
// 位运算，int为32位bit，在每个数的32位表示中，要么1要么0，因此对于某一位上出现的0或1的个数应该是3个倍数（在不考虑目标元素的条件下）。
// 因此对每一位上计算的1或0的个数之和求模3即为目标元素在该位上的值（1/0），32个位依次计算，时间O(N)
public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
int len = nums.length;
for(int i = 0; i < 32;i++){
int sum = 0;
for(int j = 0; j < len; j++){
sum += (nums[j] >> i) & 1;
}
result |= (sum % 3) << i;
}
return result;
}
}
// Single Number III
// 位运算，类同第一个问题，异或后找到的是目标两元素X,Y的异或值A，在A中32位中1代表该位上X,Y是不一样的
// 由此，将数组以该位1/0分为两组，因为成对出现的数必定同在一组，因此问题退化为问题一，在两组中分别求解目标元素
public class Solution {
public int[] singleNumber(int[] nums) {
int[] ret = new int[2];
int i,j;
int[] num1 = new int[nums.length];
int[] num2 = new int[nums.length];
int tmp = nums[0];
for(int k= 1; k< nums.length;k++){
tmp ^= nums[k];
}
int position = 0;
while(tmp%2==0){
tmp /= 2;
position++;
}
int length1=0,length2=0;
for(int k= 0,m=0,n=0; k < nums.length;k++){
if((nums[k]>>position)%2!=0){
num1[m] = nums[k];
m++;
length1 = m;
}
else {
num2[n] = nums[k];
n++;
length2 = n;
}
}
ret[0] = num1[0];
ret[1] = num2[0];
for(int k = 1; k < length1;k++)
{
ret[0] ^= num1[k];
}
for(int k = 1; k < length2;k++)
{
ret[1] ^= num2[k];
}
return ret;
}
}
