[LeetCode] 面试题 10.01.合并排序的数组

2024-10-08 21:36:55

题目：

这道题有多种实现的思路，这里使用双指针结合数组有序的特点进行解决

思路：

m代表A初始时有效元素的个数，n代表B中元素的个数，那么n+m才是A的总长度

从A的最后一个位置开始，设为cur，分别从A和B有效元素中选取最大的一个，进行比较，将较大的放入cur，随之相应的cur--，较大元素所在数组的有效个数减1

注：在进行比较时，会出现A == B的情况，此时将等号归到A<B处，B中元素优先会使得逻辑更加简单

在最后会出现两种情况：

B全部加入，A有剩余

　　这种情况下，不需再做修改，A总体已有序

A全部加入，B有剩余

　　这种情况下，说明B剩下的全是小于A中现有元素，直接依次加入A中便可

代码：

class Solution {

public:

    void merge(vector<int>& A, int m, vector<int>& B, int n) {

        int cur = m+n-;

        while(m> && n>){

            if(A[m-]>B[n-])  A[cur--] = A[m-- -];

            else   A[cur--] = B[n-- -];

        }

        while(n>){

            A[cur--] = B[n-- -];

        }

    }

};

最新文章

热门文章