LeetCode 练习——260. 只出现一次的数字 III

文章目录

1.题目描述

只出现一次的数字 III
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。

进阶:你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现?

示例 1:

输入:nums = [1,2,1,3,2,5]
输出:[3,5]
解释:[5, 3] 也是有效的答案。

示例 2:

输入:nums = [-1,0]
输出:[-1,0]

示例 3:

输入:nums = [0,1]
输出:[1,0]

2.思路

2.1 代码

由于所有数字中只有两个数(a和b)出现奇数次,其余数出现偶数次,那么将所有的数进行异或,则可以得到这两个出现奇数次的数异或结果 a ^ b。
假如 a ^ b 的结果为01101000,那么他与自己的相反(10011000)进行求或则可以得到该数右侧第一个1出现的位置(00001000),如下所示。当知道 a ^ b的右侧第一个数为1时,则a和b的该位置一定不同(异或不同为1相同为0)。那么再次遍历数组,并且数组中的数该位置为1的数进行异或运算,便可以得到a、b中的某一个数。
最后再用 a ^ b 的结果与得到的其中一个数进行异或运算,便可以得到另外一个数。
LeetCode 练习——260. 只出现一次的数字 III

class Solution {
    public int[] singleNumber(int[] nums) {
        int eor = 0;
        for (int i = 0; i < nums.length; i++) {
            eor ^= nums[i];
        }
        int rightFirstOne = eor & (-eor);
        int eorCheck = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & rightFirstOne) != 0){
                eorCheck ^= nums[i];
            }
        }
        return new int[]{eorCheck, eor^eorCheck};
    }
}

2.2 测试结果

通过测试
LeetCode 练习——260. 只出现一次的数字 III

3.总结

  • 数组中的所有数字依次异或可以得到出现奇数次的两个数异或结果
  • 一个数异或自己的相反数,便可以得到该数右边第一次1出现的位置
  • 通过第一次出现1的结果将原数组分成两拨,一拨该位置为1,另一拨该位置为0
  • 通过该位置为1的数进行异或,便得到a、b中的一个数
  • 最后通过 a ^ b ^ a = b 或者 a ^ b ^ b = a 得到另外一个数
上一篇:每日一shell(七)统计站点的IP和PV


下一篇:深入分布式缓存-Paxos