原题
给定一个整数数组 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/
相关推荐
-
leetcode9-回文数
原题 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 示例1: 输入： 121 输出： true 示例2: 输入： -121 输出： fa...
-
leetcode1144-递减元素使数组呈锯齿状
原题 给你一个整数数组 nums，每次 操作 会从中选择一个元素并 将该元素的值减少 1。 如果符合下列情况之一，则数组 A 就是 锯齿数组： 每个偶数索引对应的元素都大于相邻的元...
-
leetcode385-迷你语法分析器
原题 给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。 列表中的每个元素只可能是整数或整数嵌套列表 提示： 你可以假定这些字符串都是格式良好的： 字符串非空 字符...
-
leetcode3-无重复字符的最长子串
原题 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例1： 输入： "abcabcbb" 输出： 3 解释： 因为无重复字符的最长子串是 "abc"，所以其长...
-
剑指offer51-数组中的逆序对
原题（来源Leetcode） 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。 示例 1: 输入： [7...
-
leetcode18-四数之和
原题 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 ta...
-
leetcode66-加一
原题 给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。 你可以假设除了整数 0 之外，这个整数不会以...
-
leetcode60-第k个排列
原题 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下： "123" "132" "21...
-
leetcode232-用栈实现队列
原题 使用栈实现队列的下列操作： push(x) – 将一个元素放入队列的尾部。 pop() – 从队列首部移除元素。 peek() – 返回队列首部的元素。 empty() – ...
-
leetcode76-最小覆盖子串
原题 给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。 示例: 输入: S = "ADOBECODEBANC", T = "ABC" 输...
