【Day 71 】2021-11-19 - 260. 只出现一次的数字 III #90
Comments
思路:位运算。 方法: 位运算这个题是LeetCode136的加强版，136题中一趟异或即可搞定，这题弄一趟异或是不行的了，我们需要考虑分组处理，弄成2组，每一组满足LeetCode136的条件。 算法步骤: 对theXor, 从低位开始向高位扫描, 找出两数的异或结果中的第1个1, 这恰好是两个落单数第一个不同的bit位。 接下来, 想办法把所有数分为2组, 且每个组只有1个落单的数, 只需要找一个概率均为50%的条件即可, 比如判断与mask最高位的同一个位置的二进制位是1还是0。 剩下的操作就是和LeetCode136 的位运算解法一样了。 代码:实现语言: C++ class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int theXor = 0;
for (int num : nums) // 对nums数组中的所有数异或运算, 算出两个落单数的异或结果
theXor ^= num;
int mask = 1;
while ((theXor & mask) == 0) /* 从低位开始向高位扫描, 找出两数的异或结果中的第1个1, 这恰好是两个落单数第一个不同的bit位 */
mask <<= 1;
/* 接下来, 想办法把所有数分为2组, 且每个组只有1个落单的数, 只需要找一个概率均为50%的条件即可, 比如判断数组中的每一个元素与mask最高位的同一个位置的二进制位是1还是0 */
int group1 = 0, group2 = 0;
vector<int> res;
for (int num : nums)
{
if (num & mask)
group1 ^= num;
else group2 ^= num;
}
res = {group1, group2};
return res;
}
};复杂度分析:
|
Idea:Bitmask. Use XOR for all elements to get the XOR result (BITMASK) of two single elements. The variable BITMASK records the different bits of two single elements. Use BITMASK & (-BITMASK) to get the most right different bit (R_D) of two single elements. Use variable R_D to do the XOR again for all elements to get one single element X. The the other single element will be BITMASK^X Code:class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
mask = 0
for i in nums:
mask ^= i
d = mask & (-mask)
x = 0
for i in nums:
if i & d:
x ^= i
return [x, mask ^ x]Complexity:Time: O(N) |
|
Explanation
Python class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
a = 0
for i in nums:
a ^= i
diff = a & (-a)
b = 0
for j in nums:
if j & diff:
b ^= j
return [b, a^b] Complexity:
|
class Solution:
def singleNumber(self, nums):
s = reduce(xor, nums)
nz = s & (s-1) ^ s
num1 = reduce(xor, filter(lambda n: n & nz, nums))
return(num1, s ^ num1) |
link:https://leetcode.com/problems/single-number-iii/ 代码 Javascriptconst singleNumber = function (nums) {
let set = new Set();
nums.forEach((x) => (set.has(x) ? set.delete(x) : set.add(x)));
return Array.from(set);
}; |
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
zor = reduce(xor, nums)
res = reduce(xor, filter(lambda i: i & (zor ^ (zor & (zor - 1))), nums))
return [res,res^zor] |
思路
Java Code public int[] singleNumber(int[] nums) {
int eor = 0;
for (int n : nums) {
eor ^= n;
}
int rightOne = eor & (~eor + 1);
int eor_ = 0;
for (int n : nums) {
if ((n & rightOne) == 0) {
eor_ ^= n;
}
}
int a = eor_;
int b = eor ^ a;
return new int[]{a,b};
}时间&空间
|
|
Complexity: O(n); O(1) class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
x = reduce(xor, nums)
a = reduce(xor, filter(lambda n: n & (x&(-x)), nums))
return [a, x^a] |
思路所有数字求异或，得到的结果是两个单独数字a和b的异或xor； 代码class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int num: nums) {
xor ^= num;
}
int mask = 1;
while ((xor & mask) == 0) {
mask = mask << 1;
}
int[] ans = new int[2];
for (int num: nums) {
if ((num & mask) == 0) {
ans[0] ^= num;
} else {
ans[1] ^= num;
}
}
return ans;
}
}TC: O(n) |
Idea
Codeclass Solution {
public int[] singleNumber(int[] nums) {
int sum = 0;
for (int i : nums){
sum ^= i;
}
int mask = 1;
while ((mask & sum) == 0){
mask <<= 1;
}
int[] res = new int[2];
for (int i : nums){
if ((mask & i) == 0){
res[0] ^= i;
} else {
res[1] ^= i;
}
}
return res;
}
}Complexity
|
Problemhttps://leetcode.com/problems/single-number-iii/ Notes
Solutionclass Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for(int num: nums){
xor = xor ^ num;
}
int lowest = xor & (-xor);
int res1 = 0;
int res2 = 0;
for(int num: nums){
if((num & lowest) != 0){
res1 = res1 ^ num;
}else{
res2 = res2 ^ num;
}
}
return new int[]{res1, res2};
}
}Complexity
|
class Solution:
def singleNumber(self, A: List[int]) -> List[int]:
s = 0
for x in A:
s ^= x
y = s & (-s)
ans = [0,0]
for x in A:
if (x & y) != 0:
ans[0] ^= x
else:
ans[1] ^= x
return ans |
思路
关键点代码
C++ Code: class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
// 1. xor(a, a) = 0
//2. xor(a, 0) = xor(0, a) = a
//3. xor(1, 1) = xor(0, 0) = 0
//4. xor(1, 0) = xor(0, 1) = 1
///5. xor(a, b) = c => xor(a, c) = b and xor(b, c) = a
/// calculate c = a^ b
int bitTwoNum =0;
for(auto & it : nums)
bitTwoNum =(bitTwoNum ^ it) ;
/// find c right most
int rightMost = 1;
while( !(bitTwoNum & rightMost ) )
{
rightMost = rightMost << 1;
}
// get a or b.
int bitOneNum =0;
for(auto & it : nums)
{
if( it & rightMost)
{
bitOneNum =(bitOneNum ^ it);
}
}
// get another b or a
return {bitOneNum , bitOneNum ^ bitTwoNum} ;
}
};
|
思路先遍历一次 nums, 对于每个元素 n xorsum^= n 这样操作之后, 出现两次都数字都会被消去, 因为 i ^ i = 0, 最后 xorsum 只剩下出现一次的元素的xor, 即 xorsum = i ^ j, i, j 是 nums 中只出现了一次的元素 这个元素因为 i 和 j 只出现了一次并且不同, 所以 一定不为 0, 那么去出 这个 xorsum 的 最 least significant 1 (last_one = xorsum & -xorsum) 对于 last_one 这个元素, 因为 xor 之后是 1, 代表 只有两种情况, i & last_one = 1, j & last_one = 0 或者反过来 i & last_one = 0, j & last_one = 1 所以再次遍历数组, 用 last_one & n 将 i 和 j 区分开成为两组 分别两组做 nums1 ^= n, num2 ^= n, 之前出现两次都元素一定会被分进同一组, 于是会互相消去, i 和 j 一定会被分在两组, 于是剩下的 nums1 和 nums2 就是 i 和 j, 就是两个出现了一次的元素 class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xorsum = 0
for n in nums:
xorsum ^= n
last_one = xorsum & -xorsum
num1, num2 = 0, 0
for n in nums:
if last_one & n:
num1 ^= n
else:
num2 ^= n
return [num1, num2]复杂度时间复杂度: O(n) 两次遍历的复杂度 空间复杂度: O(1) |
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
s = set()
for num in nums:
if num in s: s.remove(num)
else: s.add(num)
return s |
思路这才是承接136的题目，那个137根本就离谱的不着边 这个题目和136很相似，136是只出现一次的数字只有一个，通过异或的位运算可以巧妙的除掉所有其他数字，但此题出现的数字有两个，那当我们异或整个数组的时候，最终我们会得到两个不同的数异或的结果，而无法将其分开。 但是实际上这个结果是保留有特征的！举例来说，假设两个只出现一次的数是6和10，他们按位异或的结果是12。改写成二进制来看就是，b'00110'和b'01010'异或得到b'01100'。想想异或的原理能发现，结果中的1表示的是6和10的“不同”，即6和10的第3位一定是不同的。 有了这个结论，我们就可以利用这一点将数组分成两个部分，一部分的第三位位0，一部分的第三位为1。此时只出现一次的两个数字6和10一定会被分开，再分别对两个部分进行之前的异或操作即可。 这里补充一个快速找到异或结果中从右边开始第一个1的方法，即 代码class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
ans = 0
for num in nums:
ans ^= num
mid = ans & -ans
ans_0, ans_1 = 0, 0
for num in nums:
if mid & num:
ans_0 ^= num
else:
ans_1 ^= num
return [ans_0, ans_1]复杂度TC: O(n) |
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
total = 0
for n in nums:
total ^= n
mask = total & (-total)
res = [0, 0]
for n in nums:
if n & mask != 0:
res[0] ^= n
else:
res[1] ^= n
return res |
代码class Solution {
public int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}复杂度时间复杂度: O(n) 空间复杂度: O(1) |
|
思路: func singleNumber(nums []int) []int {
num := 0
for i:=0;i<len(nums);i++{
num ^= nums[i]
}
lsb := num&-num
type1,type2 := 0,0
for i:=0;i<len(nums);i++{
if nums[i]&lsb > 0{
type1 ^= nums[i]
}else{
type2 ^= nums[i]
}
}
return []int{type1,type2}
}时间复杂度O（n） |
思路位运算 代码JavaScript Code var singleNumber = function (nums) {
let bitmask = 0;
for (let n of nums) {
bitmask ^= n;
}
bitmask &= -bitmask;
const ret = [0, 0];
for (let n of nums) {
if ((n & bitmask) == 0) ret[0] ^= n;
else ret[1] ^= n;
}
return ret;
};复杂度
|
思路位运算 代码class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
x=0
for i in nums:
x=x^i
t=0
while x>>t&1==0:
t+=1
a=0
b=0
for i in nums:
if i>>t&1==1:
a=a^i
else:
b=b^i
return [a,b]
|
哈希表class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
unordered_map<int, int> map;
vector<int> res;
for (auto x : nums) map[x] ++;
for (auto &[k, v]: map) {
if (v == 1) {
res.push_back(k);
}
}
return res;
}
}; |
var singleNumber = function(nums) {
let set = new Set()
for(let i of nums){
if(set.has(i)) {
set.delete(i)
}else{
set.add(i)
}
}
return [...set]
}; |
思路
代码
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for i in nums:
xor ^= i
mask = 1
while (mask & xor) == 0:
mask <<= 1
res = [0] * 2
for i in nums:
if i & mask == 0:
res[0] ^= i
else:
res[1] ^= i
return res复杂度
|
思路位运算 代码class Solution {
public int[] singleNumber(int[] nums) {
if(nums.length == 2) return nums;
int x = 0;
for(int i : nums){
x ^= i;
}
int n = 0;
for(int i = 0 ; i < 31 ;i++){
if(((x >> i) & 1) == 1){
n = i;
break;
}
}
int[] ans = new int[2];
for(int i : nums){
if(((i >> n) & 1) == 1) ans[0] ^= i;
else ans[1] ^= i;
}
return ans;
}
}复杂度分析时间复杂度：O（n） |
var singleNumber = function(nums) {
// 异或(相同为0，不同为1)
// 会消除出现两次的数字，total =会保留只出现一次的两个数字（x 和 y）之间的差异
let total = 0;
for(const i of nums){
total ^= i;
}
let diff = total & (-total);
// 从total中分离x和y
let x = 0;
for (let num of nums) {
if ((num & diff) != 0) {
x ^= num;
}
}
// 找到了x，则y = total^x
return [x, total^x];
}; |
|
class Solution { |
【day71】260. 只出现一次的数字 IIIhttps://leetcode-cn.com/problems/single-number-iii/ 思考：：存入哈希表，再找value=1的，时间复杂度是1但是空间复杂度是key。位运算可巧妙降低空间复杂度：
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = a = b = 0
length = len(nums)
for i in nums:
xor ^= i
right_bit = xor & (-xor)#取最低位为1的数
for i in nums:
if right_bit & i:
a ^= i
else:
b ^= i
return [a, b]复杂度分析：
|
思路
代码javascript /*
* @lc app=leetcode.cn id=260 lang=javascript
*
* [260] 只出现一次的数字 III
*/
// @lc code=start
/**
* @param {number[]} nums
* @return {number[]}
*/
var singleNumber = function(nums) {
// 遍历一次
// 根据题意，只有两个元素只出现一次，其他出现两次
// 全部都异或，因为相同的会约掉，最终剩下 a xor b
let xor = 0
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
xor ^= num
}
// 根据异或，两数对应位的数不同才能为1
// 找出第一个为1的位，这样就可以将两个只出现过一次的元素，分别分到两个组
let mask = 1
while ((mask & xor) === 0) {
mask <<= 1
}
const result = []
// 重新再遍历一次
for (let i = 0; i < nums.length; i++) {
const num = nums[i];
// 根据两组来遍历，每组只有一个只出现一次的元素
// 最终两组全部异或后，只剩下出现一次的元素
if ((num & mask) === 0) {
result[0] ^= num
} else {
result[1] ^= num
}
}
return result
};
// @lc code=end复杂度分析
|
思路
代码class Solution {
public int[] singleNumber(int[] nums) {
// difference between two numbers (x and y) which were seen only once
int bitmask = 0;
for (int num : nums) bitmask ^= num;
// rightmost 1-bit diff between x and y
int diff = 1;
while((bitmask & diff) == 0){
diff <<= 1;
}
int x = 0;
// bitmask which will contain only x
for (int num : nums) if ((num & diff) != 0) x ^= num;
return new int[]{x, bitmask^x};
}
}复杂度time: O(N) |
思路
代码class Solution {
public int[] singleNumber(int[] nums) {
if(nums.length == 0){ return nums;}
Map <Integer, Integer> freq = new HashMap<Integer, Integer>();
for( int num: nums){
freq.put(num, freq.getOrDefault(num,0)+1);
}
int[] ans = new int[2];
int index= 0;
for(Map.Entry<Integer, Integer> entry: freq.entrySet()){
if(entry.getValue() == 1){
ans[index++] = entry.getKey();
}
}
return ans;
}
}复杂度分析
|
思路假设答案为x1,x2, 所有元素都异或可以得到x1和x2的异或值，我卡在这里就动不了了。 看了正确答案才知道解法：x1和x2必定有一个二进制位不同，所以抓住这点就可以把所有元素分为两类，并且两类中的元素除了x1和x2外都是成双成对的，所以两类的元素分别全异或就可以得到x1和x2 class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for(int num:nums){
xor ^= num;
}
//找到一个不同的二级制位
int mask = 1;
while((mask & xor) == 0){
mask = mask << 1;
}
int[] ans = new int[2];
for(int num : nums){
if((num & mask) == 0){
ans[0] ^= num;
}else {
ans[1] ^= num;
}
}
return ans;
}
}
|
开始刷题题目简介【Day 71 】2021-11-19 - 260. 只出现一次的数字 III位运算
题目代码代码块class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int xorsum = 0;
for (int num: nums) {
xorsum ^= num;
}
// 防止溢出
int lsb = (xorsum == INT_MIN ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num: nums) {
if (num & lsb) {
type1 ^= num;
}
else {
type2 ^= num;
}
}
return {type1, type2};
}
};
复杂度
|
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
} |
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]
|
代码class Solution {
public int[] singleNumber(int[] nums) {
int xorsum = 0;
for (int num : nums) {
xorsum ^= num;
}
// 防止溢出
int lsb = (xorsum == Integer.MIN_VALUE ? xorsum : xorsum & (-xorsum));
int type1 = 0, type2 = 0;
for (int num : nums) {
if ((num & lsb) != 0) {
type1 ^= num;
} else {
type2 ^= num;
}
}
return new int[]{type1, type2};
}
}复杂度
|
class Solution {
public int[] singleNumber(int[] nums) {
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int[] ans = new int[2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() == 1) {
ans[index++] = entry.getKey();
}
}
return ans;
}
} |
|
位运算。运用到异或运算的性质: A ^ A = 0, 0 ^ A = A。因为题目中说数组中只有两个只出现一次的数字，先进行全数组异或运算，算出这两个只出现一次的数字的异或结果。之后对数组进行分组希望将这两个数字分到不同的组里。因为1 ^ 0 = 1，我们从低位开始往高位找异或运算结果中第一个出现1的数位，按照此数位进行分组，两个数字一定不在一组，其余数字在各组中一定成对出现，再次进行组内元素异或运算即可求得结果。 class Solution { } |
思路哈希表 代码`` 复杂度分析时间复杂度：O(n) 空间复杂度：O(n) |
解题思路
代码实现复杂度分析
|
思路：哈希表时间复杂度：O（n） |
class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xornum = 0
for num in nums:
xornum ^= num
lsb = xornum & (-xornum)
type1, type2 = 0, 0
for num in nums:
if num & lsb:
type1 ^= num
else:
type2 ^= num
return [type1, type2] |
【Day 71】260. 只出现一次的数字 III代码class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int ret = 0;
for (int n : nums)
ret ^= n;
int div = 1;
while ((div & ret) == 0)
div <<= 1;
int a = 0, b = 0;
for (int n : nums)
if (div & n)
a ^= n;
else
b ^= n;
return vector<int>{a, b};
}
};复杂度时间复杂度：O(N) 空间复杂度：O(1) |
思路哈希计数 代码from collections import Counter
class Solution:
def singleNumber(self, nums):
hash_nums = Counter(nums)
return [x for x in hash_nums if hash_nums[x] == 1]复杂度
|
Logic:Code:class Solution {
public int[] singleNumber(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
xor &= -xor; // to get the lowest bit different between two unique numbers
int group1 = 0, group2 = 0;
for (int cur : nums) {
if ((cur & xor) == 0) { // group 1
group1 ^= cur;
}
else { // group 2
group2 ^= cur;
}
}
return new int[]{group1, group2};
}
// bruteforce
public int[] singleNumber1(int[] nums) {
Set<Integer> numSet = new HashSet<>();
for (int num : nums) {
if (numSet.contains(num)) {
numSet.remove(num);
}
else {
numSet.add(num);
}
}
int[] res = new int[2];
int i = 0;
for (int num : numSet) {
res[i++] = num;
}
return res;
}
} |
Note
Solutionclass Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
res = [0, 0]
for n in nums:
xor ^= n
xor &= -xor
for n in nums:
if xor & n == 0:
res[0] ^= n
else:
res[1] ^= n
return resTime complexity: O(N) Space complexity: O(1) |
JAVA版本思路：主要考察的是位运算
时间复杂度：O(n)空间复杂度：O(1） |
只出现一次的数字 Ⅲ思路
代码class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = reduce(lambda x, y: x ^ y, nums)
flag = 1
while not flag & xor:
flag <<= 1
res = [0, 0]
for n in nums:
if n & flag:
res[0] ^= n
else:
res[1] ^= n
return res复杂度分析
|
class Solution {
public int[] singleNumber(int[] nums) {
Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
for (int num : nums) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
int[] ans = new int[2];
int index = 0;
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() == 1) {
ans[index++] = entry.getKey();
}
}
return ans;
}
} |
Idea:for num that appear twice, when use xor on them, the result is 0; but for num that only appear once, xor will give a non-zero result. So we can use xor on all nums in the array, the result must be a non-zero number. We then want to find out the lowest non-zero bit, which can be implemented by & with 1 and shift left. Then all nums can be divided into two types, one is when & with bit, it is nonzero, and the other is & with bit and get a zero. Maintain two int, one int is used to xor with type1 and the other is used to xor type 2. Nums that appear twice will be categorized into the same group and than canceled in xor operation. So finally the two int is the two num that appear only once. Complexity:Time: O(n) class Solution {
public int[] singleNumber(int[] nums) {
int xor=0;
for(int n: nums)
xor^=n;
int bit=1;
while((bit&xor)==0) {
bit<<=1;
}
int type1=0, type2=0;
for(int n:nums) {
if((n&bit)!=0)
type1^=n;
else
type2^=n;
}
return new int[]{type1,type2};
}
} |
Open
Intuition
Implementationclass Solution
{
public:
vector<int> singleNumber(vector<int> &nums)
{
// - bit xor operation is commutative, ie.,
// a ^ b ^ c ^ d ^ a ^ b = a ^ a ^ b ^ b ^ c ^ d = (a ^ a) ^ (b ^ b) ^ c ^ d
// - xor of same numbers resets all bits to zero, ie.,
// a ^ a = 0
// - zero xor any number is that number itself, ie., 0 ^ c = c
// suppose c and d are the different numbers that only appear once
// step 1: variable twoNums will have two non-zero bits that represent the two numbers
int twoNums{ 0 };
std::for_each(nums.begin(), nums.end(), [&twoNums](int &num) { twoNums ^= num; });
// step 2: create a one-bit mask that can be used later to tell apart the two numbers
int mask{ 1 };
while ((mask & twoNums) == 0) {
mask = mask << 1;
}
// step 3: variable mask is used to segment the two different numbers, same num will go to same category twice
std::vector<int> res(2, 0);
for (auto const &num : nums) {
if ((num & mask)) {
res[0] ^= num;
} else {
res[1] ^= num;
}
}
return res;
}
};Complexity
|
插个眼昨天晚上比较忙，有事没做。 class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int theXor = 0;
for (int num : nums) // 对nums数组中的所有数异或运算, 算出两个落单数的异或结果
theXor ^= num;
int mask = 1;
while ((theXor & mask) == 0) /* 从低位开始向高位扫描, 找出两数的异或结果中的第1个1, 这恰好是两个落单数第一个不同的bit位 */
mask <<= 1;
/* 接下来, 想办法把所有数分为2组, 且每个组只有1个落单的数, 只需要找一个概率均为50%的条件即可, 比如判断数组中的每一个元素与mask最高位的同一个位置的二进制位是1还是0 */
int group1 = 0, group2 = 0;
vector<int> res;
for (int num : nums)
{
if (num & mask)
group1 ^= num;
else group2 ^= num;
}
res = {group1, group2};
return res;
}
}; |
vector<int> singleNumber(vector<int>& nums) {
int ret = 0;
for (auto& v : nums) {
ret ^= v;
}
int firstOne = 1;
while ((firstOne & ret) == 0)
firstOne = firstOne << 1;
int a = 0, b = 0;
for (auto & v : nums) {
if ((firstOne & v) == 0)
a ^= v;
else
b ^= v;
}
return {a, b};
} |
|
思路 实现语言: C++
C++ Code:
class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int bitTwoNum =0;
for(auto & it : nums)
bitTwoNum =(bitTwoNum ^ it) ;
int rightMost = 1;
while( !(bitTwoNum & rightMost ) )
{
rightMost = rightMost << 1;
}
int bitOneNum =0;
for(auto & it : nums)
{
if( it & rightMost)
{
bitOneNum =(bitOneNum ^ it);
}
}
return {bitOneNum , bitOneNum ^ bitTwoNum} ;
}
};复杂度分析 |
|
class Solution: |
思路关键点代码
C++ Code: class Solution {
public:
vector<int> singleNumber(vector<int>& nums) {
int sum = 0;
for(int i=0;i<nums.size();i++)
sum ^= nums[i];
int res1 = 0, res2=0;
int temp = (sum==INT_MIN?sum:sum&(-sum));
for(int i=0;i<nums.size();i++)
{
if(temp&nums[i])
res1 ^= nums[i];
else
res2 ^= nums[i];
}
return {res1,res2};
}
};
复杂度分析 令 n 为数组长度。
|
XorThe point of this question is to understand that one number xor with itself will be canceled. Therefore we can xor all numbers at the first chance so that we are left with one number class Solution:
def singleNumber(self, nums: List[int]) -> List[int]:
xor = 0
for i in nums:
xor ^= i
m = 1
while m & xor == 0:
m = m<<1
a, b = 0, 0
for num in nums:
# for those numbers with 1 at bit m, it will later be reduced to only one number because it cancel itself by xor
if num & m != 0:
a ^= num
# for those numbers with 0 at bit m, it will later be reduced to only one number because it cancel itself by xor
else:
b ^= num
return [a,b]Time :O(n) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
and others
260. 只出现一次的数字 III
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/single-number-iii/
前置知识
题目描述
The text was updated successfully, but these errors were encountered: