-
Notifications
You must be signed in to change notification settings - Fork 2
/
MergeSortedArrays.java
65 lines (57 loc) · 1.52 KB
/
MergeSortedArrays.java
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
package Leetcode;
/**
* Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
*
* The number of elements initialized in nums1 and nums2 are m and n respectively.
* You may assume that nums1 has a size equal to m + n such that it has enough space to hold additional elements from nums2.
*
* Example 1:
*
* Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
* Output: [1,2,2,3,5,6]
* Example 2:
*
* Input: nums1 = [1], m = 1, nums2 = [], n = 0
* Output: [1]
*
*
* Constraints:
*
* nums1.length == m + n
* nums2.length == n
* 0 <= m, n <= 200
* 1 <= m + n <= 200
* -10^9 <= nums1[i], nums2[i] <= 10^9
*
*/
public class MergeSortedArrays {
public static void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while(i >= 0 && j >= 0) {
if(nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
} else {
nums1[k] = nums2[j];
j--;
}
k--;
}
// if any elements of nums2 still remains to be copied
while(j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
}
public static void main(String[] args) {
int[] arr1 = new int[]{1, 2, 3, 0, 0, 0};
int[] arr2 = new int[]{2, 5, 6};
merge(arr1, 3, arr2, 3);
for(int i : arr1)
System.out.print(i + ", ");
System.out.println();
}
}