LeetCode260-只出现一次的数字III

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/single-number-iii/

中文链接：https://leetcode-cn.com/problems/single-number-iii/

题目详述

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

示例 :

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

注意：

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

题目详解

  • 把所有数组元素进行异或，得到只出现一次的两个元素的异或值（记为 t）。
  • 运用 t ^ -t 得到 t 的二进制位的最后一个 1。在这个 1 所在的位，两个只出现一次的两个元素，其中一个必然在这个位上为 1，另一个为 0。据此，重新进行异或，将两个元素区分开来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class LeetCode_00260 {

    public int[] singleNumber(int[] nums) {
        int t = 0;
        for (int num : nums) {
            t ^= num;
        }
        int lastBit = t & -t;
        int t1 = 0, t2 = 0;
        for (int num : nums) {
            if ((num & lastBit) != 0) {
                t1 ^= num;
            } else {
                t2 ^= num;
            }
        }
        return new int[]{t1, t2};
    }
}