数组中只出现一次的数字

题目描述

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

解法1

利用HashMap来做这道题，时间复杂度为O(N)，空间复杂度为O(N)

代码

package nowcoder;

import java.util.HashMap;
import java.util.Map;

/**
 * @author god-jiang
 * @date 2020/1/28  16:39
 */

//一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class FindNumsAppearOnce {
    //HashMap解法
    public static void findNumsAppearOnce(int[] array, int num1[], int num2[]) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < array.length; i++) {
            if (map.containsKey(array[i])) {
                map.put(array[i], 2);
            } else {
                map.put(array[i], 1);
            }
        }
        //标识这两个数的顺序
        int count = 0;
        for (int i = 0; i < array.length; i++) {
            if (map.get(array[i]) == 1) {
                if (count == 0) {
                    num1[0] = array[i];
                    count++;
                } else {
                    num2[0] = array[i];
                }
            }
        }
    }
}

---

解法2（重点）

利用位运算中的异或运算来解这道题。异或的性质就是两个相同的数字异或为0，一个数和0异或还是它本身。要是对位运算不熟悉的话可以先看这一篇文章：

god-jiang：神级运算——位运算

用位运算可以达到时间复杂度为O(N)，空间复杂度为O(1)

思路

如果一个数组只有A和B是出现一次的数，我们把所有的数都异或了之后的结果就是A和B异或的结果。因为相同的数异或都等于0。异或的结果的二进制中至少会出现一个1，因为A和B不同，异或至少会出现一个1，我们取第一个1的位置，假设这个位置是第3位，我们把第3位为0的分成一组，把第3位为1的分成一组，各自异或，最后的结果就是出现一次的数。

代码

package nowcoder;

import java.util.HashMap;
import java.util.Map;

/**
 * @author god-jiang
 * @date 2020/1/28  17:32
 */

//一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
public class FindNumsAppearOnce {
    //异或解法
    public static void findNumsAppearOnce1(int[] array, int num1[], int num2[]) {
        int temp = 0;
        //异或的结果就是A和B的异或结果
        for (int i = 0; i < array.length; i++) {
            temp = temp ^ array[i];
        }
        int index = 1;
        //找到异或结果第一位为1的位置为index
        while ((index & temp) == 0) {
            index = index << 1;
        }
        int result1 = 0;
        int result2 = 0;
        for (int i = 0; i < array.length; i++) {
            if ((index & array[i]) == 0) {
                result1 = result1 ^ array[i];
            } else {
                result2 = result2 ^ array[i];
            }
        }
        num1[0] = result1;
        num2[0] = result2;
    }
}

结果

总结

这道题目在牛客网上还是比较经典的一道题目，可以看出你对HashMap熟不熟悉，也可以看出你对位运算的理解程度。