package Bit;

import java.util.HashMap;

import java.util.Map;

public class SingleNumberII_137 {

/**

* 时间复杂度为O(n) 空间O(n)

*/

public int singleNumber(int[] nums) {

Map<Integer,Integer> map=new HashMap<>();

for(int num:nums){

map.put(num,map.getOrDefault(num,0)+1);

}

int res=0;

for(int key:map.keySet()){

if(map.get(key)==1){

res=key;

break;

}

}

return res;

}

/**

* 时间O(nlogC) 其中C为数据范围 空间O(1)

* @param nums

* @return

*/

public int singleNumberSecond(int[] nums) {

//结果二进制形式上第i位上的值=所有num第i位上值的和对3取余的结果，因为其余数字出现3次

int res=0;

for(int i=0;i<32;i++){

int total=0;

for(int num:nums){

total+=((num>>i)&1);

}

if(total%3!=0){

res|=(1<<i);

}

}

return res;

}

}