LeetCode 之 Merge Sorted Array（排序）-蒲公英云

LeetCode 之 Merge Sorted Array（排序）

矫情吗；* 2022-08-02 15:58 209阅读 0赞

【问题描述】

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<int>& nums1, int m, vector<int>& nums2, int n) 
    {
        if (nums1.empty()) 
        {
            nums1 = nums2;
            return;
        }
        if (nums2.empty()) return ;
        qkst(nums1);
        qkst(nums2);
        vector<int> myvec;
        int k=0,j=0;
        for(int i=0;i<nums2.size()+nums1.size();i++)
        {
            // 一方耗尽怎么办
            if(k>=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<int> &vec)
    {
        return 0;
    }
    void qkst(vector<int> &vec)
    {
    }
};

3.【AC源码】

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& 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--];
        }
    }
};