欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-08 09:47:09
...

问题描述

给定两个排序后的数组 A 和 B,其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法,将 B 合并入 A 并排序。

初始化 A 和 B 的元素数量分别为 m 和 n。

示例

输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3

输出: [1,2,2,3,5,6]

思路

我们可以遍历B,对于每个B中的元素都插入到A中合适的位置。这样的时间复杂度是O(m*n). (方法一)
我们可以把数组B接在数组A的后面,然后对整个数组A进行排序。这样的时间复杂度是O((n+m)log(n+m)).(方法二)
我们可以用一个临时的数组,设置两个指针分别指向A和B的开头元素,谁小就把谁复制到新的数组中(即比较出来的是最终的位置)。最后把临时数组的值全部复制到数组A中。这样的时间复杂度是O(n+m), 空间复杂度也是O(n+m)。(方法三)
我们方法三中用临时数组的原因是,我们设置两个指针分别指向A和B的开头元素,没有办法谁小就把谁放在最终的位置,因为这可能会使我们遗失一些值。由于我们选定的某个元素的最终位置上是有元素的,直接覆盖的话我们会丢失这个值(因为指针并未更新,如果强行更新,指针也不知道该指向哪里)。But who care? 我们可以转变思维,设置两个指针指向A和B的开头元素,谁大就把谁放在最终的位置上(这样某个元素的最终位置上是没有元素的(或者可以说有元素,这个元素已经找到了自己的最终位置,可以被覆盖))。这样我们可以省去空间复杂度。 时间复杂度为O(n+m)。(方法四)

图解

为什么方法三要用临时数组?

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

方法四图解

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

方法一

Java版

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        for(int b: B){
            A[m++] = b;
            for(int i = m-1; i > 0; i--){
                if(A[i-1]>A[i]){
                    A[i-1] = A[i-1]^A[i];
                    A[i] = A[i-1]^A[i];
                    A[i-1] = A[i-1]^A[i];
                }else{
                    break;
                }
            }
        }
    }
}

方法二

Java版

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        for(int b:B){
            A[m++] = b;
        }
        Arrays.sort(A,0,m);
    }
}

方法三

Java版

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int[] tmp = new int[m+n];
        int ptrA = 0, ptrB = 0,ptrC = 0;
        while(ptrA < m && ptrB < n){
            if(A[ptrA]<=B[ptrB]){
                tmp[ptrC++] = A[ptrA++];
            }else{
                tmp[ptrC++] = B[ptrB++];
            }
        }
        while(ptrA<m){
            tmp[ptrC++] = A[ptrA++];
        }
        while(ptrB<n){
            tmp[ptrC++] = B[ptrB++];
        }
        ptrA = 0;
        for(int t: tmp){
            A[ptrA++] = t;
        }
    }
}

方法四

Java版

class Solution {
    public void merge(int[] A, int m, int[] B, int n) {
        int curHead = m+n-1;
        while(m > 0 && n > 0){
            if(A[m-1]>=B[n-1]){
                A[curHead--] = A[--m];
            }else{
                A[curHead--] = B[--n];
            }
        }
        while(m>0){
            A[curHead--] = A[--m];
        }
        while(n>0){
            A[curHead--] = B[--n];
        }
    }
}