136、只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,1]
输出: 1
示例 2:
输入: [4,1,2,1,2]
输出: 4
题解
1、利用异或运算的特点
异或运算：相同为0，不同为1
class Solution {
public int singleNumber(int[] nums) {
if (nums == null) {
return -1;
}
int ans = nums[0];
// 偶次出现的数字会被处理为0
for(int i = 1;i < nums.length;i++) {
ans ^= nums[i];
}
return ans;
}
}
137、只出现一次的数字II
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
通过HashSet
例如：[a,a,a,b,b,b,c]，可以按照下面的公式求解：
$$ c = (3 * (a + b + c) - (a + a + a + b + b + b + c)) / 2 $$
class Solution {
public int singleNumber(int[] nums) {
Set<Long> set = new HashSet<>();
// long 类型防止int类型的溢出
long sumSet = 0,sumArray = 0;
for (int n : nums) {
// 计算数组原始之和
sumArray += n;
// 统计数组元素
set.add((long)n);
}
for (Long e : set) {
sumSet += s;
}
return (int)((3 * sumSet - sumArray) / 2);
}
}
通过HashMap
统计每个数字的个数，然后输出出现次数为1的数字
class Solution {
public int singleNumber(int[] nums) {
HashMap<Integer,Integer> hashMap = new HashMap<>();
for (int num : nums) {
int pre = hashMap.getOrDefault(num, 0);
hashMap.put(num,pre+1);
}
for (int k : hashMap.keySet()) {
if (hashMap.get(k) == 1) {
return k;
}
}
return -1;
}
}
通过位运算
$$
∼x \qquad \textrm{表示} \qquad \textrm{位运算 NOT}
$$
$$
x & y \qquad \textrm{表示} \qquad \textrm{位运算 AND}
$$
$$
x \oplus y \qquad \textrm{表示} \qquad \textrm{位运算 XOR}
$$
XOR
该运算符用于检测出现奇数次的位：1、3、5 等。
0 与任何数 XOR 结果为该数。
$$
0 \oplus x = x
$$
两个相同的数 XOR 结果为 0。
$$
x \oplus x = 0
$$
以此类推，只有某个位置的数字出现奇数次时，该位的掩码才不为 0。
因此，可以检测出出现一次的位和出现三次的位，但是要注意区分这两种情况。
AND 和 NOT
为了区分出现一次的数字和出现三次的数字，使用两个位掩码：seen_once 和 seen_twice。
思路是：
仅当
seen_twice未变时，改变seen_once。仅当
seen_once未变时，改变seen_twice。
根据上图可以知道，只有位掩码 seen_once 仅保留出现一次的数字，不保留出现三次的数字。
class Solution {
public int singleNumber(int[] nums) {
int seenOnce = 0, seenTwice = 0;
for (int num : nums) {
// 数字第一次出现 ：
// 将数字与seen_once相加
// 不需要与seen_twice相加，因为已经记录在seen_once里面了
// 数字第二次出现
// seen_once 归0
// 将数字与seen_twice相加
// 数字第三次出现
// 不要将数字与seen_once相加，因为已经记录在seen_twice里面了
// seen_twice 归0
seenOnce = ~seenTwice & (seenOnce ^ num);
seenTwice = ~seenOnce & (seenTwice ^ num);
}
return seenOnce;
}
}
只出现一次的数字
给你一个整数数组 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 * 10^4$
- $2^{31} <= nums[i] <= 2^{31} - 1$
- 除两个只出现一次的整数外，nums 中的其他数字都出现两次
题解
解法1：排序 + 查找
- 暴力遍历，哈希表
- 排序遍历，枚举未出现两次的数字
class Solution {
public int[] singleNumber(int[] nums) {
if (nums.length == 2) {
return nums;
}
Arrays.sort(nums);
int[] result = new int[2];
int index= 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i-1] != nums[i]) {
result[index] = nums[i-1];
index ++;
if (i == nums.length - 1) {
result[index] = nums[i];
index++;
}
} else {
i++;
if (i == nums.length - 1) {
result[index] = nums[i];
index++;
}
}
if (index == 2) {
break;
}
}
return result;
}
}
解法2：位运算 + 分组查找
相同数字的异或结果为0，执行累加异或
多次遍历位运算，分组筛选
class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int n : nums) {
xor ^= n;
}
// 最后 xor的值是两个不相同数字的异或结果，那么低bit位的值，可以作为分组依据
// 取低bit位
int lowbit = xor & -xor;
int[] ans = new int[2];
for (int n : nums) {
ans[(n & lowbit) == 0 ? 0 : 1] ^= n;
}
return ans;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
