class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
}
};
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 - 1nums 中的其他数字都出现两次原站题解
java 解法, 执行用时: 0 ms, 内存消耗: 43.3 MB, 提交时间: 2023-10-16 09:20:18
class Solution {
public int[] singleNumber(int[] nums) {
int xorAll = 0;
for (int x : nums) {
xorAll ^= x;
}
int tz = Integer.numberOfTrailingZeros(xorAll);
int[] ans = new int[2];
for (int x : nums) {
ans[x >>> tz & 1] ^= x;
}
return ans;
}
}
rust 解法, 执行用时: 0 ms, 内存消耗: 2.3 MB, 提交时间: 2023-10-16 09:19:53
impl Solution {
pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
let xor_all = nums.iter().fold(0, |xor, &x| xor ^ x);
let tz = xor_all.trailing_zeros();
let mut ans = vec![0, 0];
for &x in &nums {
ans[x as usize >> tz & 1] ^= x;
}
ans
}
}
cpp 解法, 执行用时: 8 ms, 内存消耗: 10.1 MB, 提交时间: 2023-10-16 09:19:28
class Solution {
public:
vector<int> singleNumber(vector<int> &nums) {
unsigned int xor_all = 0;
for (int x: nums) {
xor_all ^= x;
}
int lowbit = xor_all & -xor_all;
vector<int> ans(2);
for (int x: nums) {
ans[(x & lowbit) != 0] ^= x; // 分组异或
}
return ans;
}
};
golang 解法, 执行用时: 8 ms, 内存消耗: 4.6 MB, 提交时间: 2022-11-16 11:01:00
func singleNumber(nums []int) (ans []int) {
freq := map[int]int{}
for _, num := range nums {
freq[num]++
}
for num, occ := range freq {
if occ == 1 {
ans = append(ans, num)
}
}
return
}
golang 解法, 执行用时: 8 ms, 内存消耗: 3.8 MB, 提交时间: 2022-11-16 11:00:42
func singleNumber(nums []int) []int {
xorSum := 0
for _, num := range nums {
xorSum ^= num
}
lsb := xorSum & -xorSum
type1, type2 := 0, 0
for _, num := range nums {
if num&lsb > 0 {
type1 ^= num
} else {
type2 ^= num
}
}
return []int{type1, type2}
}
python3 解法, 执行用时: 36 ms, 内存消耗: 16.2 MB, 提交时间: 2022-11-16 11:00:13
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xorsum = 0
for num in nums:
xorsum ^= num
lsb = xorsum & (-xorsum)
type1 = type2 = 0
for num in nums:
if num & lsb:
type1 ^= num
else:
type2 ^= num
return [type1, type2]
python3 解法, 执行用时: 44 ms, 内存消耗: 16.5 MB, 提交时间: 2022-11-16 10:56:53
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
freq = Counter(nums)
return [num for num, occ in freq.items() if occ == 1]