首页 > 编程语言 > 详细

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

时间:2020-07-19 17:17:09      阅读:41      评论:0      收藏:0      [点我收藏+]

原题链接

题解

方式一:利用额外的空间

开一个额外的空间存放数据,最后再放回去

代码如下
class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
        int i = 0, j = 0; int t[1010]; int k = 0;
        while(i < m && j < n){
            if(A[i] < B[j]){
                t[k ++] = A[i ++];
            }
            else{
                t[k ++] = B[j ++];
            }
        }
        while(i < m) t[k ++] = A[i ++];
        while(j < n) t[k ++] = B[j ++];
        for(int i = 0; i < n + m; ++ i){
            A[i] = t[i];
        }
    }
};

方式二:原地逆序归并

因为题目中在A中已经开了足够的空间放在后面,可以逆序的来归并,就不需要移动了,直接在原地进行操作

代码如下
class Solution {
public:
    void merge(vector<int>& A, int m, vector<int>& B, int n) {
       //使用原地逆序归并,就不需要额外的空间了
       int i = m - 1, j = n - 1, k = m + n - 1;
       while(i >= 0 && j >= 0){
           if(A[i] < B[j]) A[k --] = B[j --];
           else A[k --] = A[i --];
       }

       while(j >= 0) A[k --] = B[j --];//因为如果是A中的数据多了,那么他的顺序就直接是好的
    }
};

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

原文:https://www.cnblogs.com/Lngstart/p/13339602.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!