Skip to content

Commit 7feaecb

Browse files
yanglbmeyanglbme
committed
feat: add solutions to lc problem: No.0645. Set Mismatch
1 parent 545ee4e commit 7feaecb

File tree

6 files changed

+188
-134
lines changed

6 files changed

+188
-134
lines changed

‎README_EN.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@
1414

1515
## Introduction
1616

17-
Complete solutions to [LeetCode](https://leetcode-cn.com/problemset/all/), [LCOF](https://leetcode-cn.com/problemset/lcof/) and [LCCI](https://leetcode-cn.com/problemset/lcci/) problems, updated daily. Please give me a [star](https://github.com/doocs/leetcode) 🌟 if you like it.
17+
Complete solutions to [LeetCode](https://leetcode.com/problemset/all/), [LCOF](https://leetcode-cn.com/problemset/lcof/) and [LCCI](https://leetcode-cn.com/problemset/lcci/) problems, updated daily. Please give me a [star](https://github.com/doocs/leetcode) 🌟 if you like it.
1818

1919
[中文文档](./README.md)
2020

‎solution/0600-0699/0645.Set Mismatch/README.md

Lines changed: 86 additions & 47 deletions
Original file line numberDiff line numberDiff line change
@@ -37,16 +37,17 @@
3737
<li><code>1 <= nums[i] <= 10<sup>4</sup></code></li>
3838
</ul>
3939

40-
4140
## 解法
4241

4342
<!-- 这里可写通用的实现逻辑 -->
4443

45-
首先使用 1 到 n 的所有数字做异或运算，然后再与数组中的所有数字异或，得到的值就是缺失数字与重复的数字异或的结果。
44+
异或运算求解。
45+
46+
首先明确，两个相同的数异或之后的结果为 0。对该数组所有元素以及 `i∈[1, n]` 所有数字进行异或运算，结果就是**两个只出现一次的数字异或的结果**，即 `eor = a ^ b`。
4647

47-
接着计算中这个值中其中一个非零的位 pos。然后 pos 位是否为 1，将 nums 数组的元素分成两部分，分别异或；接着将 `1~n` 的元素也分成两部分，分别异或。得到的两部分结果分别为 a,b，即是缺失数字与重复数字。
48+
找出这个结果 eor 中最后一个二进制位为 1 而其余位为 0 的数，即 `eor & (~eor + 1)`，之后遍历数组所有元素以及 `i∈[1, n]` 所有数字，二进制位为 0 的元素异或到 a。
4849

49-
最后判断数组中是否存在 a 或 b，若存在 a，说明重复数字是 a，返回 `[a,b]`，否则返回 `[b,a]`。
50+
遍历结束后 `b = eor ^ a`，返回结果即可。
5051

5152
<!-- tabs:start -->
5253

@@ -57,28 +58,19 @@
5758
```python
5859
class Solution:
5960
def findErrorNums(self, nums: List[int]) -> List[int]:
60-
res = 0
61-
for num in nums:
62-
res ^= num
63-
for i in range(1, len(nums) + 1):
64-
res ^= i
65-
pos = 0
66-
while (res & 1) == 0:
67-
res >>= 1
68-
pos += 1
69-
a = b = 0
70-
for num in nums:
71-
if ((num >> pos) & 1) == 0:
72-
a ^= num
73-
else:
74-
b ^= num
75-
for i in range(1, len(nums) + 1):
76-
if ((i >> pos) & 1) == 0:
61+
eor, n = 0, len(nums)
62+
for i in range(1, n + 1):
63+
eor ^= (i ^ nums[i - 1])
64+
diff = eor & (~eor + 1)
65+
a = 0
66+
for i in range(1, n + 1):
67+
if (nums[i - 1] & diff) == 0:
68+
a ^= nums[i - 1]
69+
if (i & diff) == 0:
7770
a ^= i
78-
else:
79-
b ^= i
71+
b = eor ^ a
8072
for num in nums:
81-
if num == a:
73+
if a == num:
8274
return [a, b]
8375
return [b, a]
8476
```
@@ -90,35 +82,23 @@ class Solution:
9082
```java
9183
class Solution {
9284
public int[] findErrorNums(int[] nums) {
93-
int res = 0;
94-
for (int num : nums) {
95-
res ^= num;
85+
int eor = 0;
86+
for (int i = 1; i <= nums.length; ++i) {
87+
eor ^= (i ^ nums[i - 1]);
9688
}
97-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
98-
res ^= i;
99-
}
100-
int pos = 0;
101-
while ((res & 1) == 0) {
102-
res >>= 1;
103-
++pos;
104-
}
105-
int a = 0, b = 0;
106-
for (int num : nums) {
107-
if (((num >> pos) & 1) == 0) {
108-
a ^= num;
109-
} else {
110-
b ^= num;
89+
int diff = eor & (~eor + 1);
90+
int a = 0;
91+
for (int i = 1; i <= nums.length; ++i) {
92+
if ((nums[i - 1] & diff) == 0) {
93+
a ^= nums[i - 1];
11194
}
112-
}
113-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
114-
if (((i >> pos) & 1) == 0) {
95+
if ((i & diff) == 0) {
11596
a ^= i;
116-
} else {
117-
b ^= i;
11897
}
11998
}
99+
int b = eor ^ a;
120100
for (int num : nums) {
121-
if (num == a) {
101+
if (a == num) {
122102
return new int[]{a, b};
123103
}
124104
}
@@ -127,6 +107,37 @@ class Solution {
127107
}
128108
```
129109

110+
### **C++**
111+
112+
```cpp
113+
class Solution {
114+
public:
115+
vector<int> findErrorNums(vector<int>& nums) {
116+
int eor = 0, n = nums.size();
117+
for (int i = 1; i <= n; ++i) {
118+
eor ^= (i ^ nums[i - 1]);
119+
}
120+
int diff = eor & (~eor + 1);
121+
int a = 0;
122+
for (int i = 1; i <= n; ++i) {
123+
if ((nums[i - 1] & diff) == 0) {
124+
a ^= nums[i - 1];
125+
}
126+
if ((i & diff) == 0) {
127+
a ^= i;
128+
}
129+
}
130+
int b = eor ^ a;
131+
for (int num : nums) {
132+
if (a == num) {
133+
return {a, b};
134+
}
135+
}
136+
return {b, a};
137+
}
138+
};
139+
```
140+
130141
### **Go**
131142
132143
把每个数都放到它应该在的位置，最后出现“异常”的就是重复的数和丢失的数。
@@ -148,6 +159,34 @@ func findErrorNums(nums []int) []int {
148159
}
149160
```
150161

162+
也可以使用位运算。
163+
164+
```go
165+
func findErrorNums(nums []int) []int {
166+
eor, n := 0, len(nums)
167+
for i := 1; i <= n; i++ {
168+
eor ^= (i ^ nums[i-1])
169+
}
170+
diff := eor & (-eor)
171+
a := 0
172+
for i := 1; i <= n; i++ {
173+
if (nums[i-1] & diff) == 0 {
174+
a ^= nums[i-1]
175+
}
176+
if (i & diff) == 0 {
177+
a ^= i
178+
}
179+
}
180+
b := eor ^ a
181+
for _, num := range nums {
182+
if a == num {
183+
return []int{a, b}
184+
}
185+
}
186+
return []int{b, a}
187+
}
188+
```
189+
151190
### **...**
152191

153192
```

‎solution/0600-0699/0645.Set Mismatch/README_EN.md

Lines changed: 53 additions & 43 deletions
Original file line numberDiff line numberDiff line change
@@ -36,28 +36,19 @@
3636
```python
3737
class Solution:
3838
def findErrorNums(self, nums: List[int]) -> List[int]:
39-
res = 0
40-
for num in nums:
41-
res ^= num
42-
for i in range(1, len(nums) + 1):
43-
res ^= i
44-
pos = 0
45-
while (res & 1) == 0:
46-
res >>= 1
47-
pos += 1
48-
a = b = 0
49-
for num in nums:
50-
if ((num >> pos) & 1) == 0:
51-
a ^= num
52-
else:
53-
b ^= num
54-
for i in range(1, len(nums) + 1):
55-
if ((i >> pos) & 1) == 0:
39+
eor, n = 0, len(nums)
40+
for i in range(1, n + 1):
41+
eor ^= (i ^ nums[i - 1])
42+
diff = eor & (~eor + 1)
43+
a = 0
44+
for i in range(1, n + 1):
45+
if (nums[i - 1] & diff) == 0:
46+
a ^= nums[i - 1]
47+
if (i & diff) == 0:
5648
a ^= i
57-
else:
58-
b ^= i
49+
b = eor ^ a
5950
for num in nums:
60-
if num == a:
51+
if a == num:
6152
return [a, b]
6253
return [b, a]
6354
```
@@ -67,35 +58,23 @@ class Solution:
6758
```java
6859
class Solution {
6960
public int[] findErrorNums(int[] nums) {
70-
int res = 0;
71-
for (int num : nums) {
72-
res ^= num;
73-
}
74-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
75-
res ^= i;
76-
}
77-
int pos = 0;
78-
while ((res & 1) == 0) {
79-
res >>= 1;
80-
++pos;
61+
int eor = 0;
62+
for (int i = 1; i <= nums.length; ++i) {
63+
eor ^= (i ^ nums[i - 1]);
8164
}
82-
int a = 0, b = 0;
83-
for (int num : nums) {
84-
if (((num >> pos) & 1) == 0) {
85-
a ^= num;
86-
} else {
87-
b ^= num;
65+
int diff = eor & (~eor + 1);
66+
int a = 0;
67+
for (int i = 1; i <= nums.length; ++i) {
68+
if ((nums[i - 1] & diff) == 0) {
69+
a ^= nums[i - 1];
8870
}
89-
}
90-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
91-
if (((i >> pos) & 1) == 0) {
71+
if ((i & diff) == 0) {
9272
a ^= i;
93-
} else {
94-
b ^= i;
9573
}
9674
}
75+
int b = eor ^ a;
9776
for (int num : nums) {
98-
if (num == a) {
77+
if (a == num) {
9978
return new int[]{a, b};
10079
}
10180
}
@@ -104,6 +83,37 @@ class Solution {
10483
}
10584
```
10685

86+
### **C++**
87+
88+
```cpp
89+
class Solution {
90+
public:
91+
vector<int> findErrorNums(vector<int>& nums) {
92+
int eor = 0, n = nums.size();
93+
for (int i = 1; i <= n; ++i) {
94+
eor ^= (i ^ nums[i - 1]);
95+
}
96+
int diff = eor & (~eor + 1);
97+
int a = 0;
98+
for (int i = 1; i <= n; ++i) {
99+
if ((nums[i - 1] & diff) == 0) {
100+
a ^= nums[i - 1];
101+
}
102+
if ((i & diff) == 0) {
103+
a ^= i;
104+
}
105+
}
106+
int b = eor ^ a;
107+
for (int num : nums) {
108+
if (a == num) {
109+
return {a, b};
110+
}
111+
}
112+
return {b, a};
113+
}
114+
};
115+
```
116+
107117
### **Go**
108118
109119
```go

‎solution/0600-0699/0645.Set Mismatch/Solution.cpp

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
class Solution {
2+
public:
3+
vector<int> findErrorNums(vector<int>& nums) {
4+
int eor = 0, n = nums.size();
5+
for (int i = 1; i <= n; ++i) {
6+
eor ^= (i ^ nums[i - 1]);
7+
}
8+
int diff = eor & (~eor + 1);
9+
int a = 0;
10+
for (int i = 1; i <= n; ++i) {
11+
if ((nums[i - 1] & diff) == 0) {
12+
a ^= nums[i - 1];
13+
}
14+
if ((i & diff) == 0) {
15+
a ^= i;
16+
}
17+
}
18+
int b = eor ^ a;
19+
for (int num : nums) {
20+
if (a == num) {
21+
return {a, b};
22+
}
23+
}
24+
return {b, a};
25+
}
26+
};

‎solution/0600-0699/0645.Set Mismatch/Solution.java

Lines changed: 11 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -1,34 +1,22 @@
11
class Solution {
22
public int[] findErrorNums(int[] nums) {
3-
int res = 0;
4-
for (int num : nums) {
5-
res ^= num;
6-
}
7-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
8-
res ^= i;
9-
}
10-
int pos = 0;
11-
while ((res & 1) == 0) {
12-
res >>= 1;
13-
++pos;
3+
int eor = 0;
4+
for (int i = 1; i <= nums.length; ++i) {
5+
eor ^= (i ^ nums[i - 1]);
146
}
15-
int a = 0, b = 0;
16-
for (int num : nums) {
17-
if (((num >> pos) & 1) == 0) {
18-
a ^= num;
19-
} else {
20-
b ^= num;
7+
int diff = eor & (~eor + 1);
8+
int a = 0;
9+
for (int i = 1; i <= nums.length; ++i) {
10+
if ((nums[i - 1] & diff) == 0) {
11+
a ^= nums[i - 1];
2112
}
22-
}
23-
for (int i = 1, n = nums.length; i < n + 1; ++i) {
24-
if (((i >> pos) & 1) == 0) {
13+
if ((i & diff) == 0) {
2514
a ^= i;
26-
} else {
27-
b ^= i;
2815
}
2916
}
17+
int b = eor ^ a;
3018
for (int num : nums) {
31-
if (num == a) {
19+
if (a == num) {
3220
return new int[]{a, b};
3321
}
3422
}

0 commit comments

Comments
 (0)