260. 只出现一次的数字 III

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

题解

思路
暴力解法

class Solution {
    public int[] singleNumber(int[] nums) {
        int [] result=new int [2];

        int n=nums.length;
        int k=0;
        for(int i=0;i<n;i++){
            int showup=0;
            for(int j=0;j<n;j++){
                if(i==j){
                    continue;
                }else{
                    if(nums[i]==nums[j]){
                        showup=1;
                        break;
                    }
                }
            }
            if(showup==0){
                result[k]=nums[i];
                k++;
            }
        }



        return result;
    }
}

官方

在理解如何使用位运算解决本题前，读者需要首先掌握「136. 只出现一次的数字」中的位运算做法。
136. 只出现一次的数字

假设数组 nums 中只出现一次的元素分别是 x₁ 和 x₂ 。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：
x = x₁ ⊕ x₂

其中 ⊕ 表示异或运算。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a⊕b⊕b=a 抵消掉，那么最终的结果就只剩下x₁和x₂ 的异或和。

x 显然不会等于 0，因为如果x=0，那么说明 x₁ = x₂

​这样 x₁ 和 x₂就不是只出现一次的数字了。
因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l位，那么 x₁ ⊕和x₂中的某一个数的二进制表示的第 l位为 0，另一个数的二进制表示的第 l 位为 1。在这种情况下， x₁ ⊕ x₂的二进制表示的第 l位才能为 1。

这样一来，我们就可以把nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：

• 对于任意一个在数组nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；

• 对于任意一个在数组 nums 中只出现了一次的元素，即 x₁ 和 x₂，它们会被包含在不同类中。

因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x₁ ，另一类会得到 x₂ 。这样我们就找出了这两个只出现一次的元素。

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorsum = 0;
        for (int num : nums) {
            xorsum ^= num;
        }
        // 防止溢出
        int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
        int type1 = 0, type2 = 0;
        for (int num : nums) {
            if ((num & lsb) != 0) {
                type1 ^= num;
            } else {
                type2 ^= num;
            }
        }
        return new int[]{type1, type2};
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是数组 nums 的长度。

• 空间复杂度：O(1)。