【问题描写叙述】

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

1.【基础知识】

归并排序思想

常见的排序主要有两种，一种是先把待排序的序列一次切割。使子序列的长度减小至1，然后。再合并。第二种是把待排序两两分组排序然后合并。

堆排序思想

详见：

详址：http://blog.csdn.net/u013630349/article/details/46906969

2.【屌丝源代码】

未能给出完整实现！

class Solution {public:    void merge(vector
     
      & nums1, int m, vector
      
       & nums2, int n) 	{        if (nums1.empty()) 		{			nums1 = nums2;			return;		}		if (nums2.empty()) return ;		qkst(nums1);		qkst(nums2);		vector
       
         myvec;		int k=0,j=0;		for(int i=0;i
        
         =nums2.size())			{				for				nums1 = myvec;				return ;			}			if(j>=nums1.size())			{				for				nums1 = myvec;				return ;			}			if(nums1[j]>=nums2[k])			{				myvec.push_back(nums2[k]);				k++;			}			else			{				myvec.push_back(nums1[j]);				++j;						}					}		nums1 = myvec;		return ;    }	int pivot(int low,int high,vector
         
           &vec)	{		return 0;	}	void qkst(vector
          
            &vec) { }};
          
         
        
       
      
     

3.【AC源代码】

class Solution {public:    void merge(vector
     
      & nums1, int m, vector
      
       & nums2, int n) {		int ia = m - 1, ib = n - 1, icur = m + n - 1;		while(ia >= 0 && ib >= 0) {		nums1[icur--] = nums1[ia] >= nums2[ib] ?
      
     

nums1[ia--] : nums2[ib--]; } while(ib >= 0) { nums1[icur--] = nums2[ib--]; } } };

4.【算法思想】

1）遇到插入操作，最好用空间复杂度来解决时间复杂度问题；

2）插入操作，事实上操作为尾操作比为首操作的要简单、直接。

3）简单问题复杂化是最不值得的。目标为导向，干出来了，有了结果再说别的！

4）卡壳地方：a.审题；b.概念混淆；c.结果导向不明。