算法练习——合并两个有序数组

2021年2月3日每日算法练习为88. 合并两个有序数组,首先知道第一个数组的实际大小为m+n,因此不需要担心数组空间不够的问题,以第二个数组大小为准,用一个指针指向需要插入的位置,然后将后面的数往后挪,并将第二个数组的当前数字插入到指针指向的位置。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = 0, cur = 0; i < n; i++) {
while (cur < m + i && nums1[cur] <= nums2[i]) {
cur++;
}
if (cur < m + i && nums1[cur] > nums2[i]) {
for (int j = m + n - 1; j > cur; j--) {
int t = nums1[j - 1];
nums1[j - 1] = nums1[j];
nums1[j] = t;
}
nums1[cur++] = nums2[i];
} else if (cur >= m) {
nums1[cur++] = nums2[i];
}
}
}
}