只出现一次的数3 中等🌟🌟🌟
课后作业
问题描述
原文链接：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中的其他数字都出现两次
代码实现
Java
class Solution {
public int[] singleNumber(int[] nums) {
int z = 0;
for(int i = 0; i < nums.length; i++){
z = z ^ nums[i];
}
// m 表示第几个二进制位不同
int m = 1;
while((m & z) == 0){
m = m << 1;
}
int x = 0;
int y = 0;
for(int i = 0; i < nums.length; i++){
if((nums[i] & m) == 0){
// 不需要额外new一个数组，直接计算就行
x = x ^ nums[i];
}else{
y = y ^ nums[i];
}
}
return new int[]{x, y};
}
}
Python
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
z = 0
for i in range(len(nums)):
z = z ^ nums[i]
m = 1
while (m & z) == 0:
m = m << 1
x = 0
y = 0
for i in range(len(nums)):
if (nums[i] & m) == 0:
x = x ^ nums[i]
else:
y = y ^ nums[i]
return [x, y]
C++
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int z = 0;
for (int i = 0; i < nums.size(); i++) {
z = z ^ nums[i];
}
int m = 1;
while ((m & z) == 0) {
m = m << 1;
}
int x = 0;
int y = 0;
for (int i = 0; i < nums.size(); i++) {
if ((nums[i] & m) == 0) {
x = x ^ nums[i];
} else {
y = y ^ nums[i];
}
}
return {x, y};
}
};
Go
func singleNumber(nums []int) []int {
z := 0
for i := 0; i < len(nums); i++ {
z = z ^ nums[i]
}
m := 1
for (m & z) == 0 {
m = m << 1
}
x := 0
y := 0
for i := 0; i < len(nums); i++ {
if (nums[i] & m) == 0 {
x = x ^ nums[i]
} else {
y = y ^ nums[i]
}
}
return []int{x, y}
}