- Nuggets team number online, help you Offer impromptu! Click here for more details
Subject core
A simple algorithm every day to prevent Alzheimer’s disease
Topic describes
Merge nums2 into nums1 to make nums1 an ordered array.
Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.
Example 1: Input nums1 = [1,2,3,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Nums1 = [1], m = 1, nums2 = [], n = 0 nums1.length == m + n nums2.length == n 0 <= m, n <= 200 1 <= m + n <= 200 -109 <= nums1[i], nums2[i] <= 109Copy the code
Their thinking
The easiest way to do this is to iterate through the nums1 array and insert the values of the NUMs2 array.
Double pointer: nums1 and NUMs2 are two sorted arrays, so you can use this double pointer to achieve O(m+n) time complexity, O(m+n) space complexity algorithm.
Reverse double pointer: given that the length of n in the last half of NUMs1 is empty, we can use reverse double pointer for comparison interpolation. Achieve O(1) space complexity.
The problem solving code
Simple solution of violence
public void merge(int[] nums1, int m, int[] nums2, int n) {
for(int i=0; i<m+n; i++){if(i>=m){
nums1[i]=nums2[i-m];
}
}
Arrays.sort(nums1);
}
Copy the code
Double pointer
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) {// if p1==m Then insert nums2
cur = nums2[p2];
p2++;
} else if(p2 ==n) {if p2==n, the right side is finished. Nums1 cur = nums1[p1]; p1++; }else if (nums1[p1] < nums2[p2]) {
Nums1 [0]; nums2[0]
// If the left is less than the right, then p1 increases
cur = nums1[p1];// Insert p1 into the sorted array
p1++;
} else {// Insert p2 into the sorted array
cur = nums2[p2];
p2++;
}
sorted[p1 + p2 - 1] = cur;
}
for (int i = 0; i != m + n; ++i) {
nums1[i] = sorted[i];
}
}
Copy the code
Reverse double pointer
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m - 1, p2 = n - 1;// The left pointer is the last digit in nums1, and the right pointer is the last digit in nums2
int tail = m + n - 1;// Start in reverse order with subscript m+n-1
int cur;
while (p1 >= 0 || p2 >= 0) {//p1, p2 is less than 0
if (p1 == -1) {
cur = nums2[p2];
p2--;
} else if (p2 == -1) {
cur = nums1[p1];
p1--;
} else if (nums1[p1] > nums2[p2]) {// Compare the size of the rightmost nums1 and nums2
cur = nums1[p1];//nums1 is larger than nums2
p1--;//p1 moves to the left
} else {
cur = nums2[p2];// Instead, P2 moves to the left
p2--;
}
nums1[tail] = cur;// assign value=0 to the right of nums1tail--; }}Copy the code
# # to summarize
Simple algorithm, for preventing senile dementia, very good 👌