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

英文原文

Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.

You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.

 

Example 1:

Input: nums = [1,2,1,3,2,5]
Output: [3,5]
Explanation:  [5, 3] is also a valid answer.

Example 2:

Input: nums = [-1,0]
Output: [-1,0]

Example 3:

Input: nums = [0,1]
Output: [1,0]

 

Constraints:

• 2 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• Each integer in nums will appear twice, only two integers will appear once.

中文题目

给定一个整数数组 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 <= nums.length <= 3 * 104
• -231 <= nums[i] <= 231 - 1
• 除两个只出现一次的整数外，nums 中的其他数字都出现两次

通过代码

高赞题解

解题思路

第一步：
把所有的元素进行异或操作，最终得到一个异或值。因为是不同的两个数字，所以这个值必定不为 0；

int xor = 0;
 for (int num : nums) {
     xor ^= num;
 } 

第二步：
取异或值最后一个二进制位为 1 的数字作为 mask，如果是 1 则表示两个数字在这一位上不同。

int mask = xor & (-xor);

第三步：
通过与这个 mask 进行与操作，如果为 0 的分为一个数组，为 1 的分为另一个数组。这样就把问题降低成了：“有一个数组每个数字都出现两次，有一个数字只出现了一次，求出该数字”。对这两个子问题分别进行全异或就可以得到两个解。也就是最终的数组了。

int[] ans = new int[2];
for (int num : nums) {
    if ( (num & mask) == 0) {
        ans[0] ^= num;
    } else {
        ans[1] ^= num;
    }
}

复杂度分析：
时间复杂度 $O(N)$，空间复杂度 $O(1)$

统计信息

通过次数	提交次数	AC比率
78721	106214	74.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
只出现一次的数字	简单
只出现一次的数字 II	中等