原题
给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。
示例：
输入: [1,2,1,3,2,5] 输出: [3,5]
注意：
- 结果输出的顺序并不重要，对于上面的例子，
[5, 3]也是正确答案。 - 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
解法
思想
如果不限制常数空间复杂度用哈希表计数可以很容易做出来，但是限制了空间复杂度，可以用位运算：
只看题目，和leetcode136-只出现一次的数字很相似，对于唯一一个只出现一次的数字，我们可以通过异或将其找出，这道题有两个只出现一次的数字，如果将所有的数字异或，结果并不能显示是哪两个数字只出现一次。可以想办法将这些数字分为两组，并将两个不同的数字分到不同的组中，再进行查找。
那么如何将两个不同的数字分到两个不同的组中呢，可以使用第一次将全部数字异或的结果，得到的结果其实就是这两个数字异或的结果。因为这两个数字不一样，得到的异或结果也必定有至少一位是1。只要将这一位是1的数字分为一组，是0的数字分为一组，就能将所有数字分为两组，而这两组中只有一个只出现一次的数字，异或的结果就是这个数字。
代码
class Solution {
public int[] singleNumbers(int[] nums) {
int k = 0;
for(int num: nums) {
k ^= num;
}
int mask = 1;
//找到k中最靠近低位的1
while((k & mask) == 0) {
mask <<= 1;
}
int a = 0;
int b = 0;
//使用掩码进行与运算，结果是0分为一组，结果是1分为一组
for(int num: nums) {
if((num & mask) == 0) {
a ^= num;
} else {
b ^= num;
}
}
return new int[]{a, b};
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode260-%e5%8f%aa%e5%87%ba%e7%8e%b0%e4%b8%80%e6%ac%a1%e7%9a%84%e6%95%b0%e5%ad%97iii/
相关推荐
-
程序员面试金典17.16-按摩师
原题（来源Leetcode） 一个有名的按摩师会收到源源不断的预约请求，每个预约都可以选择接或不接。在每次预约服务之间要有休息时间，因此她不能接受相邻的预约。给定一个预约请求序列，...
-
leetcode234-回文链表
原题 请判断一个链表是否为回文链表。 示例1： 输入： 1->2 输出： false 示例2： 输入： 1->2->2->1 输出： true 进阶: 你能否用 O(n) 时间复杂...
-
leetcode1248-统计「优美子数组」
原题 给你一个整数数组 nums 和一个整数 k。 如果某个 连续 子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。 请返回这个数组中「优美子数组」的数目。 ...
-
leetcode95-不同的二叉搜索树II
原题 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: [ [1,null,3,2], &n...
-
leetcode82-删除排序链表中的重复元素II
原题 给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。 示例 1: 输入: 1->2->3->3->4->4->5 输出: 1->2->5 示...
-
leetcode36-有效的数独
原题 判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-...
-
leetcode150-逆波兰表达式求值
原题 根据逆波兰表示法，求表达式的值。 有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。 说明： 整数除法只保留整数部分。 给定逆波兰...
-
leetcode8-字符串转换整数 (atoi)
原题 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下： 如果第一个...
-
leetcode173-二叉搜索树迭代器
原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例： BSTIterator iterator...
-
leetcode914-卡牌分组
原题 给定一副牌，每张牌上都写着一个整数。 此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组： 每组都有 X 张牌。 组内所有的牌上都写着相同的整数。...
