fueanta

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