題目描述：
給一個(gè)整型數(shù)組宛篇，除了一個(gè)整數(shù)只出現(xiàn)一次芹务，其他所有整數(shù)均出現(xiàn)兩次，找出給唯一出現(xiàn)一次的數(shù)分析：
位運(yùn)算亡哄，利用位運(yùn)算的性質(zhì)做題枝缔，出現(xiàn)過兩次基本上代表了異或結(jié)果為0，數(shù)組所有元素異或最終結(jié)果就是目標(biāo)元素
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;
}
}
- 擴(kuò)展
- Single Number II：除一個(gè)元素出現(xiàn)一次之外蚊惯，其他元素均出現(xiàn)三次愿卸，求該唯一元素
- Single Number III：除兩個(gè)元素出現(xiàn)一次之外，其他元素均出現(xiàn)過兩次截型，求這兩個(gè)元素
// Single Number II
// 位運(yùn)算短绸，int為32位bit霎槐，在每個(gè)數(shù)的32位表示中毯辅，要么1要么0菇篡，因此對于某一位上出現(xiàn)的0或1的個(gè)數(shù)應(yīng)該是3個(gè)倍數(shù)（在不考慮目標(biāo)元素的條件下）。
// 因此對每一位上計(jì)算的1或0的個(gè)數(shù)之和求模3即為目標(biāo)元素在該位上的值（1/0）波闹，32個(gè)位依次計(jì)算酝豪，時(shí)間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
// 位運(yùn)算，類同第一個(gè)問題舔痪，異或后找到的是目標(biāo)兩元素X,Y的異或值A(chǔ)寓调，在A中32位中1代表該位上X,Y是不一樣的
// 由此，將數(shù)組以該位1/0分為兩組锄码，因?yàn)槌蓪Τ霈F(xiàn)的數(shù)必定同在一組，因此問題退化為問題一晌涕，在兩組中分別求解目標(biāo)元素
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;
}
}
