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 中只出现一次的元素分别是 x1 和 x2 。如果把 nums 中的所有元素全部异或起来，得到结果 x，那么一定有：
x = x1 ⊕ x2
其中 ⊕ 表示异或运算。这是因为 nums 中出现两次的元素都会因为异或运算的性质 a⊕b⊕b=a 抵消掉，那么最终的结果就只剩下x1和x2 的异或和。
x 显然不会等于 0，因为如果x=0，那么说明 x1 = x2
这样 x1 和 x2就不是只出现一次的数字了。
因此，我们可以使用位运算 x & -x 取出 x 的二进制表示中最低位那个 1，设其为第 l位，那么 x1 ⊕和x2中的某一个数的二进制表示的第 l位为 0，另一个数的二进制表示的第 l 位为 1。在这种情况下， x1 ⊕ x2的二进制表示的第 l位才能为 1。
这样一来，我们就可以把nums 中的所有元素分成两类，其中一类包含所有二进制表示的第 l 位为 0 的数，另一类包含所有二进制表示的第 l 位为 1 的数。可以发现：
对于任意一个在数组nums 中出现两次的元素，该元素的两次出现会被包含在同一类中；
对于任意一个在数组 nums 中只出现了一次的元素，即 x1 和 x2，它们会被包含在不同类中。
因此，如果我们将每一类的元素全部异或起来，那么其中一类会得到 x1 ，另一类会得到 x2 。这样我们就找出了这两个只出现一次的元素。
作者：LeetCode-Solution
来源：力扣（LeetCode）
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)。
