[C++知识库]easy 合并两个有序数组 双指针

要求原地修改nums1

双指针(逆向)：

c++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1;
        int j=n-1;
        int last =m+n-1;

        while(i>=0 && j>=0){
            if(nums1[i]>=nums2[j]){
                nums1[last] = nums1[i];
                i--;
                last--;
            }else{
                nums1[last] = nums2[j];
                j--;
                last--;
            }
        }
        //cout<<i<<" "<< j<<" "<< last<<endl;  // 比完有数组会剩

        while(i>=0){
            nums1[last] = nums1[i];
            i--;
            last--;
        }  
        while(j>=0){
            nums1[last] = nums2[j];
            j--;
            last--;
        }    
        
    }
};

双指针：

c++

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> nums(m + n);
        int i=0,j=0;
        int t=0;
        while((i < m )|| (j < n)){
            if(i==m){
                nums[t]=nums2[j];
                t++;
                j++;
            }else if(j==n){
                nums[t]=nums1[i];
                t++;
                i++;               
            }else if(nums1[i] >= nums2[j]){
                nums[t]=nums2[j];
                t++;
                j++;
            }else{
                nums[t]=nums1[i];
                t++;
                i++;
            }
        }

        for(int i=0;i<m+n;i++){
            nums1[i] = nums[i];
        }
    }
};

sort 函数排序：

c++

先将数组nums2放进数组nums1的尾部，然后直接对整个数组进行排序。

class Solution {
public:
    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());
    }
};

python

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1[m:]=nums2
        nums1.sort()