
问题
给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
- The number of elements initialized in nums1 and nums2 are m and n respectively.
- You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.
Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
示例
public class Program { public static void Main(string[] args) { int[] nums1 = { 1, 3, 5, 7, 9, 0, 0, 0, 0, 0 }; int[] nums2 = { 2, 4, 6, 8, 10 }; Merge(nums1, 5, nums2, 5); ShowArray(nums1); Console.ReadKey(); } private static void ShowArray(int[] array) { foreach(var num in array) { Console.Write($"{num} "); } Console.WriteLine(); } private static void Merge(int[] nums1, int m, int[] nums2, int n) { //双指针法扫描数组 int point1 = m - 1; int point2 = n - 1; //指针,试图向第1个数组从后往前填充数值 int index = m + n - 1; //从后往前扫描双数组 while(point1 >= 0 && point2 >= 0) { //如果数组1中的值大,则将数组1中的数据放入数组1中的后面部分 if(nums1[point1] > nums2[point2]) { nums1[index--] = nums1[point1--]; //否则,则将数组2中的数据放入数组1中的后面部分 } else { nums1[index--] = nums2[point2--]; } } //当数组2中的值提前结束时,复制数组1中余下的部分 while(point1 >= 0) { nums1[index--] = nums1[point1--]; } //当数组1中的值提前结束时,复制数组2中余下的部分 while(point2 >= 0) { nums1[index--] = nums2[point2--]; } } }
以上给出1种算法实现,以下是这个案例的输出结果:
1 2 3 4 5 6 7 8 9 10
分析:
显而易见,以上参考算法在最坏的情况下的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3686。