题目

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路 + 代码

思路1

利用Map统计每个数字出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int num: array){
            if(!map.containsKey(num))
                map.put(num, 1);
            else
                map.put(num, map.get(num)+1);
        }
        for(Map.Entry<Integer, Integer> entry: map.entrySet()){
            if(entry.getValue()==1)
                list.add(entry.getKey());
        }
        num1[0] = list.get(0);
        num2[0] = list.get(1);
    }
}

思路2

与题目只出现一次的数字类似，利用异或的知识。

唯一不同是这次是找出两个只出现一次的数字，所以需要找到这两个不同数字的区别，然后分别异或。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int dif=0;
        for(int num: array)
            dif ^= num;
        // dif=1100 -dif=0100, dif &= -dif  dif=0100,即只保存最右侧异或结果不同的那一位，分割数组
        dif &= -dif;
        for(int num: array){
            if((num & dif)==0)
                num1[0] ^= num;
            else
                num2[0] ^= num;
        }
    }
}

类似题目