8000 update · zykjcom/leetcode@036d9b9 · GitHub
[go: up one dir, main page]
Skip to content

Commit 036d9b9

Browse files
feiyutalkfeiyutalk
committed
update
1 parent a7fa754 commit 036d9b9

File tree

3 files changed

+38
-21
lines changed

3 files changed

+38
-21
lines changed

‎problems/136. Single Number/README.md

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,5 +19,3 @@ class Solution {
1919
}
2020
```
2121

22-
23-

‎problems/231. Power of Two/images/Power_of_Two.png

-18 KB
Binary file not shown.

‎problems/260. Single Number III/README.md

Lines changed: 38 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,6 @@
11
# 260. Single Number III
2-
## Description
3-
4-
```
5-
Difficulty: Medium
6-
```
7-
Given an array of numbers 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.
8-
9-
For example:
10-
11-
Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].
12-
13-
**Note:**
14-
15-
1. The order of the result is not important. So in the above example, [5, 3] is also correct.
16-
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
17-
## Solution 1
18-
我们可以利用HashMap这种数据结构来记录元素及其属性，那么这道题的属性就是该元素出现的次数。当我们把这个数据结构构建起来之后，算法就简单了，只要去遍历就可以了。这样的解法时间复杂度和空间复杂度都是O(n)的。
2+
## #1 暴力搜索[AC]
3+
我们可以利用HashMap这种数据结构来记录元素及其属性，那么这道题的属性就是该元素出现的次数。当我们把这个数据结构构建起来之后，算法就简单了，只要去遍历就可以了。这样的解法时间复杂度和空间复杂度都是O(n)的。
194

205
```java
216

@@ -41,6 +26,40 @@ class Solution {
4126
}
4227
```
4328

44-
***
29+
- 时间复杂度：$O(n)$
30+
- 空间复杂度：$O(n)$
31+
32+
## #2 位操作[AC]
33+
34+
这道题目用位操作来求解有一定的难度。
35+
36+
**思路**
37+
38+
- **第一步**：肯定还是像我们上面的解法一样，所有数进行`异或`，不过最终得到的结果是 a 和 b（假设 a 和 b 是落单的数字）两个值的异或结果 a XOR b，没有直接得到 a 和 b 的值；
39+
- **第二步：**想办法得到 a 或者 b，假设 aXORb 为 `00001001`（F肯定不为0），根据 aXORb 的值我们发现，`值为1的位`（比如从右向左第一位）表示在此位上 a 和 b 的值不同；所以，根据这个特点，我们首先得到从右往左的第一个1，通过`aXORb & -aXORb`得到。
40+
- **第三步**：第二步中得到的了最后一个位置上的1，这个1表示，在该位置上，a和b是不一样的，也就是有可能该位置a为0，b为1；也有可能a为1，b为0。我们根据这个特点来得到a，b。请注意，在这一步，我们仍然遍历整个数组，在结果数组进行存储的时候，我们采用`res ^= num`的方式，还记得吗？那些重复的元素会通过这个操作被过滤掉，只剩下出现一次的元素，而我们在条件里加了`diff & num == 0`这个条件来区分`a`和`b`。
41+
42+
```java
43+
class Solution {
44+
public int[] singleNumber(int[] nums) {
45+
if(nums == null || nums.length == 0)
46+
return new int[0];
47+
int[] res = new int[2];
48+
int diff = 0;
49+
for(int num : nums)
50+
diff ^= num;
51+
// then the diff store the result : a ^ b
52+
diff &= -diff; // get the last 1
53+
for(int num : nums){
54+
if((diff & num) == 0)
55+
res[0] ^= num;
56+
else
57+
res[1] ^= num;
58+
}
59+
return res;
60+
}
61+
}
62+
```
63+
64+
4565

46-
**enjoy life, coding now! :D**

0 commit comments

Comments
 (0)
0