LeetCode刷题（34）～合并两个有序数组

题目描述

给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。

说明:

初始化 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]

  

 

  
1
  
2
  
3
  
4
 

解答 By 海轰

提交代码(合并+排序)

 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i=0;i<n;++i) nums1[m+i]=nums2[i]; sort(nums1.begin(),nums1.end()); }

  

 

  
1
  
2
  
3
  
4
  
5
 

运行结果

提交代码（寻找最大数）

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { int x=m+n-1; int len1=m-1; int len2=n-1; while(len1>=0&&len2>=0) { if(nums1[len1]>nums2[len2]) nums1[x--]=nums1[len1--]; else nums1[x--]=nums2[len2--]; } while(len1>=0) nums1[x--]=nums1[len1--]; while(len2>=0) nums1[x--]=nums2[len2--]; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
 

运行结果

提交代码（优化版本）

void merge(vector<int>& nums1, int m, vector<int>& 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--]); //nums1[i--]=nums1[m--]; } swap(nums1[i--], nums2[n--]); //  nums1[i--]=nums2[n--]; } }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
 

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-sorted-array
参考：https://leetcode-cn.com/problems/merge-sorted-array/solution/he-bing-liang-ge-you-xu-shu-zu-by-leetcode/

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/107922417