This article is participating in the "Java Topics month - Java brush title punch" to view details about active links
Title description
This is 88 on LeetCode. Combine two ordered arrays .
Tag: "Dual pointer", "Sort"
Given two ordered integer arrays nums1 and nums2, please merge nums2 into nums1 to make nums1 an ordered array.
Initialize the number of elements of nums1 and nums2 to m and n respectively.
You can assume that the space size of nums1 is equal to m + n, so that it has enough space to store the 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] Copy code
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Copy code
prompt:
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- - <= nums1[i], nums2[i] <=
Double pointer (extra space)
A simple approach is to create one and array of equal length , using a double pointer to and data is migrated to .
Finally copied to .
Code:
class Solution {
public void merge ( int [] nums1, int m, int [] nums2, int n) {
int total = m + n;
int [] arr = new int [total];
int idx = 0 ;
for ( int i = 0 , j = 0 ; i <m || j <n;) {
if (i <m && j <n) {
arr[idx++] = nums1[i] <nums2[j]? nums1[i++]: nums2[j++];
} else if (i <m) {
arr[idx++] = nums1[i++];
} else if (j <n) {
arr[idx++] = nums2[j++];
}
}
System.arraycopy(arr, 0 , nums1, 0 , total);
}
}
Copy code
- time complexity:
- Space complexity:
Merge first and then sort
We can also The content of is first migrated to go again for sorting.
Code:
class Solution {
public void merge ( int [] nums1, int m, int [] nums2, int n) {
System.arraycopy(nums2, 0 , nums1, m, n);
Arrays.sort(nums1);
}
}
Copy code
- time complexity:
- Space complexity:
PS. The sort sort in Java is a comprehensive sort. Including insertion/dual-axis quick sorting/merge/timsort, it is assumed here
In-situ merger (from front to back)
You can also directly performs the merge operation, but you need to ensure that each cycle starts,The pointer of must point to the smallest element.
Therefore, we need to performs partial sorting.
Code:
class Solution {
public void merge ( int [] nums1, int m, int [] nums2, int n) {
int i = 0 , j = 0 ;
while (j <n) {
if (i >= m) {
nums1[i] = nums2[j++];
} else {
int a = nums1[i], b = nums2[j];
if (a> b) swap(nums1, i, nums2, j);
sort(nums2, j, n- 1 );
}
i++;
}
}
void sort ( int [] nums, int l, int r) {
if (l >= r) return ;
int x = nums[l], i = l- 1 , j = r + 1 ;
while (i <j) {
do i++; while (nums[i] <x);
do j--; while (nums[j]> x);
if (i <j) swap(nums, i, nums, j);
}
sort(nums, l, j);
sort(nums, j + 1 , r);
}
void swap ( int [] nums1, int i, int [] nums2, int j) {
int tmp = nums1[i];
nums1[i] = nums2[j];
nums2[j] = tmp;
}
}
Copy code
- time complexity:
- Space complexity: ignore the recursive overhead, the complexity is
In-situ merger (from back to front)
The idea is similar to "Method 1". It can be done by adjusting the traversal direction from "from front to back" to "from back to front". Space complexity.
Code:
class Solution {
public void merge ( int [] nums1, int m, int [] nums2, int n) {
int i = m- 1 , j = n- 1 ;
int idx = m + n- 1 ;
while (i> = 0 || j >= 0 ) {
if (i >= 0 && j >= 0 ) {
nums1[idx--] = nums1[i] >= nums2[j]? nums1[i--]: nums2[j--];
} else if (i >= 0 ) {
nums1[idx--] = nums1[i--];
} else {
nums1[idx--] = nums2[j--];
}
}
}
}
Copy code
- time complexity:
- Space complexity:
At last
This is the first in our series of articles on "Brush through LeetCode"
In this series of articles, in addition to explaining the problem-solving ideas, the most concise code will be given as much as possible. If a general solution is involved, the corresponding code template will also be provided.
In order to make it easier for all students to debug and submit code on the computer, I have established a related warehouse: github.com/SharingSour...
In the warehouse address, you can see the link to the solution of the series of articles, the corresponding code of the series of articles, the link to the original question of LeetCode and other preferred solutions.