Title Description

Here are two ordered integer arrays nums1 and nums2. Please merge nums2 into nums1 to make num1 an ordered array.

Explain:

• The number of elements to initialize nums1 and nums2 is m and n, respectively.
• You can assume that nums1 has enough space (space size greater than or equal to m + n) to hold the elements in nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]

My solution

Internally create a vector to store the results, and then swap them with the swap function.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> temp;
        int i = 0;
        int j = 0;
        
        while(i < m && j < n)
        {
            if(nums1[i] < nums2[j]) temp.push_back(nums1[i++]);
            
            else temp.push_back(nums2[j++]);
        }
        
        for(i; i < m; i++)
        {
            temp.push_back(nums1[i]);
        }
        
        for(j; j < n; j++)
        {
            temp.push_back(nums2[j]);
        }
        
        nums1.swap(temp);
    }
};

Other solution 1: direct assignment without push back

You should know that in the conditions given by the question, why does nums1 add 0? It's not for the convenience of assignment

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;  // Last of nums1
        int j = n - 1;  // Last of nums2
        int k = m + n - 1;  // Last of mixed arrays

        while(i >= 0 && j >=0)
        {
            if(nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }

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

Other solution 2: simplification of solution 1

Combine the two while of the other solution 1.

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m - 1;  // Last of nums1
        int j = n - 1;  // Last of nums2
        int k = m + n - 1;  // Last of mixed arrays

        while(j >=0)
        {
            if( i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
            else nums1[k--] = nums2[j--];
        }
    }
};

Other solutions 3-5: using vector's own api

Although these solutions are not quite in line with the investigation points of the problem, let's see. The main purpose is to learn how to use the api flexibly

Solution 3: the newly saved data is nums1 data from start to m, then insert nums2, then swap the newly created vector and nums1, and finally sort them with sort.

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    vector<int> temp(nums1.begin(), nums1.begin() + m);
    temp.insert(temp.end(), nums2.begin(), nums2.end());
    nums1.swap(temp);
    sort(nums1.begin(), nums1.end());
}

Solution 4: remove the 0 after nums1, insert nums2 after nums1, and sort.

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    nums1.resize(m);
    nums1.insert(nums1.end(), nums2.begin(), nums2.end());
    sort(nums1.begin(), nums1.end());

Solution 5: use copy to directly change the data behind the m of nums1 into the data of nums2, and then execute sort.

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n)
{
    copy(nums2.begin(),nums2.end(),nums1.begin() + m);
    sort(nums1.begin(), nums1.end());