leetcode-88. 合并两个有序数组 · Aaray
题面
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
样例
1. 输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
2. 输入:nums1 = [0], m = 0 nums2 = [6], n = 1 输出: [6]
算法
时间复杂度：O(n+m)
与合并有序链表类似。
1. 如果m为0，直接返回就可以了。如果n为0,则需要把nums2中前n个元素都搬到nums1中，返回。
2. 如果，m、n都不为0，计算合并后的元素数len = m+n, 我们从后往前为nums1[len--]赋max(nums1[m]nums2[n]), 之后较大的数组下标自减（已经比较后填入了nums1中），直到某个数组被遍历完。
3. 如果2之后，m == 0,那么代表nums1中的元素都已经填完了，就把nums2中剩下的元素按次序填入nums1中即可；如果 n == 0，即nums2填完了，那就结束，剩下的nums1本来就是有序的。
源码
1 class Solution { 2 public: 3 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { 4 if(n == 0) 5 return ; 6 else if(m == 0) 7 { 8 for(int i=0; i<n; i++) 9 nums1[i] = nums2[i]; 10 } 11 12 //从往前放置 13 int len = m+n-1; 14 m--; n--; 15 while(m >= 0 && n >= 0 && len >= 0) 16 { 17 if(nums1[m] < nums2[n]) 18 { 19 nums1[len] = nums2[n]; 20 len--; n--; 21 } 22 else 23 { 24 nums1[len] = nums1[m]; 25 len--; m--; 26 } 27 } 28 if(m < 0) 29 { 30 for(int i=0; i<=n; i++) 31 nums1[i] = nums2[i]; 32 } 33 } 34 };
拼多多集团-PDD工作强度 281人发布
我现在也只有一个保底