[LeetCode][88. Merge Sorted Array] 3 Approaches: Sorting, Two Pointers and Reverse Two Pointers
By Long Luo
This article is the solution 3 Approaches: Sorting, Two Pointers and Reverse Two Pointers of Problem 88. Merge Sorted Array.
Here shows 3 Approaches to slove this problem: Sorting, Two Pointers and Reverse Two Pointers.
Sorting
Let the array into the rear of array , and then sort the entire array.
1 | public static void merge_sort(int[] nums1, int m, int[] nums2, int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Two Pointers
Since two arrays and are both sorted in non-decreasing order, so we can use the Two Pointers method.
We consider the two arrays as two queues, takes the smaller numbers from the two arrays headers each round and put it into our results.
1 | public static void merge(int[] nums1, int m, int[] nums2, int n) { |
Analysis
- Time Complexity: .
- Space Complexity: .
Reverse Two Pointers
Since the extra space of is in the back, it’s better to process the sorted data from the back to the front, fill in the values while traversing the array.
Let two pointers and to point to the tails of and , traversal from the tail and compare the values, and set the pointer to point to the end of . After each traversal of the size of the comparison value, it will be filled.
When , the traversal ends. If the data of is not copied completely, we can copy the rest to the front of , and finally we got the answer.
The process is show as the following images.
1 | class Solution { |
Analysis
- Time Complexity: .
- Space Complexity: .
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)
Explore More Leetcode Solutions. 😉😃💗