
题目链接:https://leetcode.com/problems/single-number-ii/description/
题目大意:给出一串数,每个数都出现三次,只有一个数只出现一次,把这个出现一次的数找出来。
法一:利用hashMap,空间换时间,但是好像也没怎么换到时间。代码如下(耗时15ms):
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int ans = -1;
for(int i = 0; i < nums.length; i++) {
if(map.containsKey(nums[i])) {
map.put(nums[i], map.get(nums[i]) + 1);
}
else {
map.put(nums[i], 1);
}
}
for(int i = 0; i < nums.length; i++) {
if(map.get(nums[i]) == 1) {
ans = nums[i];
break;
}
}
return ans;
}
法二:先排序,再一一计算。代码如下(耗时5ms):
public int singleNumber(int[] nums) {
Arrays.sort(nums);
int ans = nums[0];
int cnt = 1;
int length = nums.length;
for(int i = 1; i < length; i++) {
if(nums[i] != nums[i - 1]) {
if(cnt == 1) {
break;
}
ans = nums[i];
cnt = 1;
}
else {
cnt++;
}
}
return ans;
}
法三(借鉴):利用位运算,这个方法是普遍方法,136题也可以用这个方法做,但是时间复杂度其实是o(n^2),所以也不是最优的,只是用到了位运算。借鉴自:http://blog.****.net/feliciafay/article/details/19004479。代码如下(耗时7ms):
public int singleNumber(int[] nums) {
int ans = 0;
int length = nums.length;
//将每一个数取二进制位按位相加,如果都是重复的则当前位的相加和一定是3的倍数,否则当前位一定存在于要找的那个数中
//比如1,1,1,2,2,2,3这六个数将其转为二进制数按位相加,然后每一位都对3取模,最后一定可以得到3
for(int i = 0; i < 32; i++) {//计算每一位
int sum = 0;//统计每一位的和
for(int j = 0; j < length; j++) {//对每个数取第i位的数值
if(((nums[j] >> i) & 1) == 1) {//取第i位的数值
sum++;//将每个数第i位的值相加求和
sum %= 3;
}
}
if(sum != 0) {//如果对3取模后非0,则说明当前位一定是要找的数的某一位
ans |= sum << i;//将其转为十进制加入结果当中
}
}
return ans;
}
法四(借鉴):这个位运算还没看懂。https://www.cnblogs.com/yangrouchuan/p/5323327.html
链接:https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811
来源:牛客网 /**
* 数组中有两个出现一次的数字,其他数字都出现两次,找出这两个数字
* @param array
* @param num1
* @param num2
*/
public static void findNumsAppearOnce(int [] array,int num1[] , int num2[]) {
if(array == null || array.length <= 1){
num1[0] = num2[0] = 0;
return;
}
int len = array.length, index = 0, sum = 0;
for(int i = 0; i < len; i++){
sum ^= array[i];
}
for(index = 0; index < 32; index++){
if((sum & (1 << index)) != 0) break;
}
for(int i = 0; i < len; i++){
if((array[i] & (1 << index))!=0){
num2[0] ^= array[i];
}else{
num1[0] ^= array[i];
}
}
}
/**
* 数组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;
}