## 剑指Offer（Java版）：数组出现一次的数字 原

一贱书生

* 请些程序找出这两个只出现一次的数字。要求时间复杂度为O(n),空间复杂度为O(1)

Java实现的代码如下：

package cglib;

public class jiekou {
public void findNumsAppearOnce(int[] arr){
if(arr == null)
return;
int number = 0;
for(int i: arr)
{
System.out.println("number="+number);
System.out.println("i="+i);
number^=i;
System.out.println("与i异或后：number="+number);
}
int index = findFirstBitIs1(number);
int number1= 0,number2 = 0;
for(int i : arr){
if(isBit1(i,index))
number1^=i;
else
number2^=i;
}
System.out.println(number1);
System.out.println(number2);
}
private int findFirstBitIs1(int number){
System.out.println("findFirstBitIs1:number="+number);
int indexBit = 0;
System.out.println("findFirstBitIs1:indexBit="+indexBit);
while((number & 1)== 0){
System.out.println("findFirstBitIs1:number & 1=0");
number = number >> 1;
System.out.println("findFirstBitIs1:number>> 1="+number);
++indexBit;
System.out.println("findFirstBitIs1:++indexBit="+indexBit);
}
return indexBit;
}
private boolean isBit1(int number,int index){
System.out.println("isBit1:number="+number);
System.out.println("isBit1:index="+index);
number = number >>index;

System.out.println("isBit1:number >>index="+number);
return (number & 1) == 0;
}
public static void main(String[] args){
int[] arr={6,2,4,3,3,2,5,5};
jiekou test = new jiekou();
test.findNumsAppearOnce(arr);
}
}

number=0
i=6

number=6
i=2

number=4
i=4

number=0
i=3

number=3
i=3

number=0
i=2

number=2
i=5

number=7
i=5

findFirstBitIs1:number=2
findFirstBitIs1:indexBit=0
findFirstBitIs1:number & 1=0
findFirstBitIs1:number>> 1=1
findFirstBitIs1:++indexBit=1
isBit1:number=6
isBit1:index=1
isBit1:number >>index=3
isBit1:number=2
isBit1:index=1
isBit1:number >>index=1
isBit1:number=4
isBit1:index=1
isBit1:number >>index=2
isBit1:number=3
isBit1:index=1
isBit1:number >>index=1
isBit1:number=3
isBit1:index=1
isBit1:number >>index=1
isBit1:number=2
isBit1:index=1
isBit1:number >>index=1
isBit1:number=5
isBit1:index=1
isBit1:number >>index=2
isBit1:number=5
isBit1:index=1
isBit1:number >>index=2
4
6

package cglib;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Map.Entry;

public class jiekou {
/**
*  如果数组中没有x，那么数组中所有的数字都出现了3次，在二进制上，每位上1的个数肯定也能被3整除。如{1, 5, 1, 5, 1, 5}从二进制上看有：

1：0001

5：0101

1：0001

5：0101

1：0001

5：0101

*
*
*/

/**
* 数组a中只有一个数出现一次，其他数都出现了2次，找出这个数字
* @param a
* @return
*/
public static int find1From2(int[] a){
int len = a.length, res = 0;
for(int i = 0; i < len; i++){
res = res ^ a[i];
}
return res;
}
/**
* 数组a中只有一个数出现一次，其他数字都出现了3次，找出这个数字
* @param a
* @return
*/
public static int find1From3(int[] a){
int[] bits = new int[32];
int len = a.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < 32; j++){
bits[j] = bits[j] + ( (a[i]>>>j) & 1);
}
}
int res = 0;
for(int i = 0; i < 32; i++){
if(bits[i] % 3 !=0){
res = res | (1 << i);
}
}
return res;
}

/**
* 数组a中只有一个数出现2次，其他数字都出现了4次，找出这个数字
* @param a
* @return
*/
public static void find1From6(int[] a){

Map<Integer,Integer> map=new HashMap<Integer,Integer>();
for(int i=0;i<a.length;i++){
Integer num=map.get(a[i]);
if(num!=null){
map.put(a[i],++num);
}else{
map.put(a[i],1);
}
}
int n=2; //设置输出指定次数的值
Iterator<Entry<Integer,Integer>> ite=map.entrySet().iterator();
while(ite.hasNext()){
Entry<Integer,Integer> entry=ite.next();
if(entry.getValue() == n){
System.out.println("出现次数为"+n+"次的数字有:"+entry.getKey());
}

}

}
/**
* 数组a中只有一个数出现一次，其他数字都出现了5次，找出这个数字
* @param a
* @return
*/

public static int find1From5(int[] a){
int[] bits = new int[32];
int len = a.length;
for(int i = 0; i < len; i++){
for(int j = 0; j < 32; j++){
bits[j] = bits[j] + ( (a[i]>>>j) & 1);
}
}
int res = 0;
for(int i = 0; i < 32; i++){
if(bits[i] % 5 !=0){
res = res | (1 << i);
}
}
return res;
}

public static void main(String[] args){

int[] arr2={6,2,2,3,3,4,4};
int[] arr3={2,4,4,4,3,3,3};
int[] arr5={8,2,2,2,2,2,4,4,4,4,4};
int[] arr6={1,1,1,1,2,2,3,3,3,3,4,4};

System.out.println(find1From2(arr2));
System.out.println(find1From3(arr3));
System.out.println(find1From5(arr5));
find1From6(arr6);

}
}

6
2
8

### 一贱书生

Tom-shushu
2018/07/28
0
0

firepation
2018/10/10
0
0
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

2018/09/04
0
0

chenyu_insist
01/07
0
0

2017/12/04
0
0

Java8

package com.shi.lambda;import java.util.Arrays;import java.util.List;import org.junit.Test;import com.shi.model.Employee;/** * 初始化案例 * @author xiaosh......

30分钟前
1
0
c# 动态编译代码

31分钟前
3
0

33分钟前
2
0
tomcat 与 spring boot 设置虚拟路径

tomcat 设置虚拟路径 <Context path="/uploadDir" docBase="/data"/>path是请求访问的路径docBase是服务器存储文件的路径,Linux 根目录下 data spring boot 虚拟路径设置 registry.addRe......

kdy1994
36分钟前
1
0
var ，let ，const 的区别和共同点

MrBoyce
41分钟前
1
0