[数据结构与算法]LeetCode 88 | 合并两个有序数组

LeetCode 88 | 合并两个有序数组

题目

题解

1. 投机做法就是直接用sor排序啦，居然过了。。。

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

2. 但是身为技术人还是自己写写算法。基本思想就是两个数组从后往前扫描，谁大谁从后往前插进去。

class Solution {
public:
    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--]);
            }
            swap(nums1[i--], nums2[n--]);
        }
    }
};