Skip to content

LeetCode-面试题56-1-数组中数字出现的次数

题目

一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

示例1:

输入:nums = [4,1,4,6]
输出:[1,6] 或 [6,1]

示例 2:

输入:nums = [1,2,10,4,1,4,3,3]
输出:[2,10] 或 [10,2]
  • 限制:

    2 <= nums.length <= 10000

解题思路

异或运算(单1为1,其余0):

根据异或运算的特点,相同的数字会在异或的时候抵消了,不相同的数字,其不相同的位会被保留

如果数组中有2个数字是不相同的,所以对数组整体异或之后,剩下的数字肯定至少有一位为1

如果能够找到第一个为1的那一位,那么就能够通过判断这一位是否为1,而划分数组为2个子数组

这样问题就分解成了,分别寻找2个子数组中,只出现一次的数字

由于判断位的条件具有二分性,当判断出一个不相同的数字位为1时,另一个数字该位则不为1,于是划分的子数组中自然一个数组会包含一个不相同数字

Java代码

java
class Solution {
    public int[] singleNumbers(int[] nums) {
        int temp=0;
        // 数组整体异或
        for(int i:nums)
            temp^=i;
        // 初始化mask=1
        int mask = 1;
        // 通过mask,判断第一次出现1的位数
        while((temp&mask)==0){
            mask<<=1;
        }
        int num1 = 0;
        int num2 = 0;
        for(int j:nums){
            // 通过判断1出现的位置和数组元素与运算结果是否为0,来二分数组
            if((j&mask)==0){ // 相同的数字会分在一起,但不同的数字会因此隔开
                num1^=j;
            }else{
                num2^=j;
            }
        }
        return new int[]{num1,num2};
    }
}