# LeetCode 88: Merge Sorted Array.

Mar 24th, 2020
206
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. /*
2. Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
3.
4. Note:
5. -----
6. 1. The number of elements initialized in nums1 and nums2 are m and n respectively.
7. 2. You may assume that nums1 has enough space (size that is greater or equal to m + n)
8.    to hold additional elements from nums2.
9.
10. Examples:
11. ---------
12. Input:
13. nums1 = [1,2,3,0,0,0], m = 3
14. nums2 = [2,5,6],       n = 3
15.
16. Output: [1,2,2,3,5,6]
17. ----------------------------
18. Input:
19. nums1 = [1,2,3,0,0,0,0,0,0], m = 3
20. nums2 = [2,5,6,7,8,9],       n = 6
21.
22. Output: [1,2,2,3,5,6]
23. ----------------------------
24. Input:
25. nums1 = [0], m = 0
26. nums2 = [1], n = 1
27.
28. Output: [1]
29. */
30.
31. namespace Problems.LeetCode.Array.MergeSortedArray_88
32. {
33.     public class Solution
34.     {
35.         /// <summary>
36.         ///     Merges two sorted arrays, one into another, in ascending order.
37.         ///     Uses three pointers on two arrays.
38.         ///     Time complexity : O(n)
39.         ///     Space complexity : O(1)
40.         /// </summary>
41.         /// <param name="nums1">An array of integers.</param>
42.         /// <param name="m">Number of non zero elements in nums1.</param>
43.         /// <param name="nums2">An array of integers.</param>
44.         /// <param name="n">Number of elements in nums2.</param>
45.         public void Merge(int[] nums1, int m, int[] nums2, int n)
46.         {
47.             if (n == 0)
48.                 return;
49.
50.             int ptr1 = m - 1, ptr2 = n - 1, ptr3 = m + n - 1;
51.
52.             while (ptr1 > -1 && ptr2 > -1)
53.             {
54.                 nums1[ptr3--] = (nums1[ptr1] > nums2[ptr2]) ? nums1[ptr1--] : nums2[ptr2--];
55.             }
56.
57.             while (ptr1 > -1)
58.             {
59.                 nums1[ptr3--] = nums1[ptr1--];
60.             }
61.
62.             while (ptr2 > -1)
63.             {
64.                 nums1[ptr3--] = nums2[ptr2--];
65.             }
66.         }
67.
68.         /// <summary>
69.         ///     Merges two sorted arrays, one into another, in ascending order.
70.         ///     Uses sorting.
71.         ///     Time complexity : O(nlgn)
72.         ///     Space complexity : O(1)
73.         /// </summary>
74.         /// <param name="nums1">An array of integers.</param>
75.         /// <param name="m">Number of non zero elements in nums1.</param>
76.         /// <param name="nums2">An array of integers.</param>
77.         /// <param name="n">Number of elements in nums2..</param>
78.         public void Merge2(int[] nums1, int m, int[] nums2, int n)
79.         {
80.             for (var i = m + n - 1; i > m - 1; i--)
81.                 nums1[i] = nums2[m + n - (i + 1)];
82.             System.Array.Sort(nums1);
83.         }
84.     }
85. }
RAW Paste Data