Cracking the coding interview--Q9.1

January 16, 2013
作者:Hawstein
出处:http://hawstein.com/posts/9.1.html
声明:本文采用以下协议进行授权: 自由转载-非商用-非衍生-保持署名|Creative Commons BY-NC-ND 3.0 ,转载请注明作者及出处。

题目

原文:

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.

译文:

A和B是两个有序数组(假设为递增序列),而且A的长度足以放下A和B中所有的元素, 写一个函数将数组B融入数组A,并使其有序。

解答

最简单的方法是开一个大小可以容纳A和B的数组C,然后像归并排序中合并两个数组一样, 按照大小顺序把数组A和数组B的元素一一地放入数组C,然后再将数组C拷贝给A。 这种方法额外地使用了O(n)的空间,显然这是没有必要的开销。由于A的大小已经足够用了, 所以直接在A上直接操作即可。

可是如果我们思维定势地对比数组A和数组B,每次取小的元素放入数组A, 这样就会发现,要放入的位置上正放着有用的元素。处理起来就麻烦了。

相反,如果我们从A和B的尾部元素开始对比,每次取大的元素放在数组A的尾部, 这样一来,要放入的位置就不会出现上面的冲突问题。当对比结束时, 即可得到一个排好序的数组A。代码如下:

#include <iostream>
using namespace std;

void merge(int a[], int b[], int n, int m){
    int k = n + m - 1;
    int i = n - 1, j = m - 1;
    while(i>=0 && j>=0){
        if(a[i] > b[j]) a[k--] = a[i--];
        else a[k--] = b[j--];
    }
    while(j>=0) a[k--] = b[j--];
}

int main(){
    int a[15] = {
        1, 3, 7, 8, 9
    };
    int b[] = {
        2, 4, 5, 6, 10
    };
    int n = 5, m = 5;
    merge(a, b, 5, 5);
    for(int i=0; i<m+n; ++i)
        cout<<a[i]<<" ";
    return 0;
}

对比结束后,要检查数组B中是否还有元素,有的话要将它们拷贝到数组A。 我们并不需要检查数组A,因为如果数组A还有元素,说明while循环是因为数组B 中没有元素了才退出的。而A中的元素本来就是有序且就位于数组A中,所以不需要再管它。 如果A和B中的元素个数为n和m,则该算法的时间复杂度为O(n+m)。

让我们再加点限制条件,如果两个有序的序列并且没有额外的空间,那要怎么排序。 比如对于数组A,它的前半段和后半段分别有序,不使用额外的空间怎么使A整体有序。

首先,不可避免的我们还是要将两个有序部分中的元素拿出来对比。 我们先拿出前半段的第一个元素和后半段的第一个元素进行对比, 如果后半段的第一个元素要小,就将它们交换。由于这两个元素是各自序列的最小值, 这一对比就将整个数组A的最小值取出放在了正确的位置上。然后呢? 交换到后半段的那个值怎么办?不理它,不太合适吧。我们可以通过两两对比, 把它移动到后半段的某个位置,使后半段保持有序。接下来呢? 我们取出前半段的第2个元素(第1个元素已经放在它正确的位置上,不用理它了), 还是和后半段的第1个元素对比,这一对比中较小的就会是整个数组中第2小的元素, 如果是后半段那个元素较小,则交换它们,然后仍然移动后半段使其保持有序。 这样不断进行下去,当把前半段的元素都遍历操作一遍,就会将小的元素都移动到前半段, 并且是有序的。而大的元素都在后半段且也是有序的。排序结束。

代码如下:

#include <iostream>
using namespace std;

void swap(int &a, int &b){
    a = a^b;
    b = a^b;
    a = a^b;
}
void merge(int a[], int begin, int mid , int end){
    for(int i=begin; i<=mid; ++i){
        if(a[i]>a[mid+1]){
            swap(a[i], a[mid+1]);
            for(int j=mid+1; j<end; ++j){
                if(a[j]<=a[j+1]) break;
                swap(a[j], a[j+1]);
            }
        }
    }
}
int main(){
    int a[10] = {
        8, 9, 11, 15, 17, 1, 3, 5, 12, 18
    };
    int b[10] = {
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10
    };
    merge(a, 0, 4, 9);
    for(int i=0; i<10; ++i)
        cout<<a[i]<<" ";
    return 0;
}

全书题解目录:

Cracking the coding interview–问题与解答

全书的C++代码托管在Github上:

https://github.com/Hawstein/cracking-the-coding-interview