leetcode260-只出现一次的数字III

原题

给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。

示例:

输入: [1,2,1,3,2,5] 输出: [3,5]

注意:

  1. 结果输出的顺序并不重要,对于上面的例子, [5, 3] 也是正确答案。
  2. 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

解法

思想

如果不限制常数空间复杂度用哈希表计数可以很容易做出来,但是限制了空间复杂度,可以用位运算:

只看题目,和leetcode136-只出现一次的数字很相似,对于唯一一个只出现一次的数字,我们可以通过异或将其找出,这道题有两个只出现一次的数字,如果将所有的数字异或,结果并不能显示是哪两个数字只出现一次。可以想办法将这些数字分为两组,并将两个不同的数字分到不同的组中,再进行查找。

那么如何将两个不同的数字分到两个不同的组中呢,可以使用第一次将全部数字异或的结果,得到的结果其实就是这两个数字异或的结果。因为这两个数字不一样,得到的异或结果也必定有至少一位是1。只要将这一位是1的数字分为一组,是0的数字分为一组,就能将所有数字分为两组,而这两组中只有一个只出现一次的数字,异或的结果就是这个数字。

代码

class Solution {
    public int[] singleNumbers(int[] nums) {
        int k = 0;
        for(int num: nums) {
            k ^= num;
        }
        int mask = 1;

        //找到k中最靠近低位的1
        while((k & mask) == 0) {
            mask <<= 1;
        }

        int a = 0;
        int b = 0;

        //使用掩码进行与运算,结果是0分为一组,结果是1分为一组
        for(int num: nums) {
            if((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }

        return new int[]{a, b};
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode260-%e5%8f%aa%e5%87%ba%e7%8e%b0%e4%b8%80%e6%ac%a1%e7%9a%84%e6%95%b0%e5%ad%97iii/

发表回复

登录后才能评论