说明
工作之后重新刷算法，主要是用java刷算法，读书期间用python/c++刷算法偏多，一来python写起来快很多，而来c++的性能有笔java高很多，所以当时java显得不伦不类。但因为现在的工作语言是java，所以开始用java进行刷算法。同时可以试试go吧，因为刷算法是快速熟悉一门语言的途径，想了解下go，所以刷算法的时候可以用用go。
总结
解1
nums2拼接到nums1的尾部，直接sort
java
解2：双指针
代码详情
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
|
my solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (m == 0) {
System.arraycopy(nums2,0, nums1, 0, n);
}
if (n == 0) {
return;
}
int[] combined = new int[m + n];
int oneIdx = 0;
int twoIdx = 0;
for (int i = 0; i < m + n; i++) {
if (oneIdx < m && twoIdx < n) {
if (nums1[oneIdx] < nums2[twoIdx]) {
combined[i] = nums1[oneIdx];
oneIdx += 1;
} else {
combined[i] = nums2[twoIdx];
twoIdx += 1;
}
continue;
}
if (twoIdx >= n && oneIdx < m) {
combined[i] = nums1[oneIdx];
oneIdx += 1;
continue;
}
if (oneIdx >= m && twoIdx < n) {
combined[i] = nums2[twoIdx];
twoIdx += 1;
}
}
System.arraycopy(combined, 0, nums1, 0, m + n);
}
}
|
我的代码待优化的地方
解3：逆向双指针
官方题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = 0, p2 = 0;
int[] sorted = new int[m + n];
int cur;
while (p1 < m || p2 < n) {
if (p1 == m) {
cur = nums2[p2++];
} else if (p2 == n) {
cur = nums1[p1++];
} else if (nums1[p1] < nums2[p2]) {
cur = nums1[p1++];
} else {
cur = nums2[p2++];
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
}
|
拓展阅读
- 快速排序的时间复杂度：快速排序的最坏运行情况是 O(n²)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。
我的方法
尾移法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int removeElement(int[] nums, int val) {
int removeNum = 0;
if (nums.length != 0 && nums[0] == val) {
removeNum++;
}
for (int i = 1; i < nums.length; i++) {
nums[i - removeNum] = nums[i];
if (nums[i] == val) {
removeNum++;
}
}
return nums.length - removeNum;
}
}
|
我的思路可以优化的地方
1
2
3
4
5
6
7
| public int removeElement(int[] nums, int val) {
int idx = 0;
for (int x : nums) {
if (x != val) nums[idx++] = x;
}
return idx;
}
|
</details>
双指针
代码详情
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length;
while (left < right) {
if (nums[left] == val) {
nums[left] = nums[right - 1];
right--;
} else {
left++;
}
}
return left;
}
}
|
一种分析
官方题解
