本文共 2584 字,大约阅读时间需要 8 分钟。
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。 说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。 示例:输入:nums1 = [1,2,3,0,0,0], m = 3nums2 = [2,5,6], n = 3输出:[1,2,2,3,5,6] 提示:-10^9 <= nums1[i], nums2[i] <= 10^9nums1.length == m + nnums2.length == n作者:力扣 (LeetCode)链接:https://leetcode-cn.com/leetbook/read/top-interview-questions/xmi2l7/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
最朴素的思路,就是判断大小:
nums1[i]>nums2[j]
时,nums1的i及其之后元素后移,将nums2[j]
插入到i的位置,将m,i,j加1; nums1[i]<=nums2[j]
时,i+=1; 可以利用额外的数组空间降低复杂度。
class Solution { public: void vector_insert(vector & nums1, int i, int m, int num){ for(int j=m-1;j>=i;j-=1){ nums1[j+1]=nums1[j]; } nums1[i]=num; } void merge(vector & nums1, int m, vector & nums2, int n) { if(m==0){ nums1=nums2; return; } int i=0,j=0; while(i
用temp存储nums1的数据,用temp和nums2进行大小比较,存入nums1中
class Solution { public: void merge(vector & nums1, int m, vector & nums2, int n) { vector temp(nums1); //初始化m为nums1的拷贝 int i = 0, j = 0, k = 0; while(i <= m-1 && j <= n-1) { if(temp[i] < nums2[j]) nums1[k++] = temp[i++]; else nums1[k++] = nums2[j++]; } while(i <= m-1) { nums1[n+i] = temp[i]; i++; } while(j <= n-1) { nums1[m+j] = nums2[j]; j++; } }};/*作者:zrita链接:https://leetcode-cn.com/problems/merge-sorted-array/solution/c-san-chong-fang-fa-z-by-zrita/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。*/
大的先走~~
void merge(vector & nums1, int m, vector & nums2, int n) { int i = nums1.size() - 1; m--; n--; while (n >= 0) { while (m >= 0 && nums1[m] > nums2[n]) { swap(nums1[i--], nums1[m--]); } swap(nums1[i--], nums2[n--]); }}/*作者:ikaruga链接:https://leetcode-cn.com/problems/merge-sorted-array/solution/88-by-ikaruga/来源:力扣(LeetCode)著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。*/
class Solution { public: void merge(int A[], int m, int B[], int n) { int i = m - 1, j = n - 1, index = m + n - 1; while (i >= 0 && j >= 0) A[index--] = A[i] > B[j] ? A[i--] : B[j--]; while (j >= 0) A[index--] = B[j--]; }};