-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathMergeSortedArray.java
More file actions
76 lines (68 loc) · 1.85 KB
/
Copy pathMergeSortedArray.java
File metadata and controls
76 lines (68 loc) · 1.85 KB
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package two_pointer;
import java.util.Arrays;
class MergeSortedArray {
public static void main(String[] args) {
// int[] num1 = new int[]{1, 2, 3, 0, 0, 0};
int[] num1 = new int[]{4, 5, 6, 0, 0, 0};
// new Solution().merge(num1, 3, new int[]{2, 5, 6}, 3);
new MergeSortedArray().merge1(num1, 3, new int[]{1, 2, 3}, 3);
System.out.println(Arrays.toString(num1));
}
public void merge1(int[] nums1, int m, int[] nums2, int n) {
if (m + n != nums1.length || n < 1) {
return;
}
int[] new_arr = Arrays.copyOf(nums1, m);
int i = 0;
int k = 0;
int current = 0;
while (i < m && k < n) {
int num1 = new_arr[i];
int num2 = nums2[k];
if (num1 > num2) {
nums1[current] = num2;
k++;
} else {
nums1[current] = num1;
i++;
}
current++;
}
while (i < m) {
nums1[current] = new_arr[i];
current++;
i++;
}
while (k < n) {
nums1[current] = nums2[k];
current++;
k++;
}
}
// more efficient
public void merge2(int[] nums1, int m, int[] nums2, int n) {
if (m + n != nums1.length || n < 1) {
return;
}
int p1 = m - 1;
int p2 = n - 1;
int p3 = nums1.length - 1;
while (p1 >= 0 && p2 >= 0) {
int num1 = nums1[p1];
int num2 = nums2[p2];
if (num1 > num2) {
nums1[p3] = num1;
p1--;
} else {
nums1[p3] = num2;
p2--;
}
p3--;
}
while (p2 >= 0) {
nums1[p3] = nums2[p2];
p2--;
p3--;
}
}
}