代码拉取完成，页面将自动刷新
Given an integer array nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once. You can return the answer in any order.
You must write an algorithm that runs in linear runtime complexity and uses only constant extra space.
Example 1:
Input: nums = [1,2,1,3,2,5] Output: [3,5] Explanation: [5, 3] is also a valid answer.
Example 2:
Input: nums = [-1,0] Output: [-1,0]
Example 3:
Input: nums = [0,1] Output: [1,0]
Constraints:
2 <= nums.length <= 3 * 104-231 <= nums[i] <= 231 - 1nums will appear twice, only two integers will appear once.The XOR operation has the following properties:
Since all numbers in the array appear twice except for two numbers, we can perform XOR operation on all numbers in the array to get the XOR result of the two numbers that only appear once.
Since these two numbers are not equal, there is at least one bit that is 1 in the XOR result. We can use the lowbit operation to find the lowest bit of 1 in the XOR result, and divide all numbers in the array into two groups based on whether this bit is 1 or not. This way, the two numbers that only appear once are separated into different groups.
Perform XOR operation on each group separately to obtain the two numbers $a$ and $b$ that only appear once.
The time complexity is $O(n)$, where $n$ is the length of the array. The space complexity is $O(1)$.
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xs = reduce(xor, nums)
a = 0
lb = xs & -xs
for x in nums:
if x & lb:
a ^= x
b = xs ^ a
return [a, b]
class Solution {
public int[] singleNumber(int[] nums) {
int xs = 0;
for (int x : nums) {
xs ^= x;
}
int lb = xs & -xs;
int a = 0;
for (int x : nums) {
if ((x & lb) != 0) {
a ^= x;
}
}
int b = xs ^ a;
return new int[] {a, b};
}
}
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
long long xs = 0;
for (int& x : nums) {
xs ^= x;
}
int lb = xs & -xs;
int a = 0;
for (int& x : nums) {
if (x & lb) {
a ^= x;
}
}
int b = xs ^ a;
return {a, b};
}
};
func singleNumber(nums []int) []int {
xs := 0
for _, x := range nums {
xs ^= x
}
lb := xs & -xs
a := 0
for _, x := range nums {
if x&lb != 0 {
a ^= x
}
}
b := xs ^ a
return []int{a, b}
}
function singleNumber(nums: number[]): number[] {
const xs = nums.reduce((a, b) => a ^ b);
const lb = xs & -xs;
let a = 0;
for (const x of nums) {
if (x & lb) {
a ^= x;
}
}
const b = xs ^ a;
return [a, b];
}
impl Solution {
pub fn single_number(nums: Vec<i32>) -> Vec<i32> {
let xs = nums.iter().fold(0, |r, v| r ^ v);
let lb = xs & -xs;
let mut a = 0;
for x in &nums {
if (x & lb) != 0 {
a ^= x;
}
}
let b = xs ^ a;
vec![a, b]
}
}
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumber = function (nums) {
const xs = nums.reduce((a, b) => a ^ b);
const lb = xs & -xs;
let a = 0;
for (const x of nums) {
if (x & lb) {
a ^= x;
}
}
const b = xs ^ a;
return [a, b];
};
public class Solution {
public int[] SingleNumber(int[] nums) {
int xs = nums.Aggregate(0, (a, b) => a ^ b);
int lb = xs & -xs;
int a = 0;
foreach(int x in nums) {
if ((x & lb) != 0) {
a ^= x;
}
}
int b = xs ^ a;
return new int[] {a, b};
}
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。