Question

Java编程:两个int类型有序数组A和B，长度分别为m和n，合并成有序数组C，并给出时间复杂度。

Java编程:两个int类型有序数组A和B，长度分别为m和n，合并成有序数组C，并给出时间复杂度。

Answer 1

//两个有序的话，那么只用每次都从头部开始取值，然后插入到C数组里面
//所以时间复杂度为O(m+n)
public void mergeArray(int[] a,int[] b,int[] c){
    int m = 0;
    int n = 0;
    int x = 0;
    while(m<a.length&& n<b.length){
        if(a[m]<= b[n]){
            c[x++]=a[m++];
        }else{
            c[x++]=b[n++];
        }
    }
}

Answer 2

private static void mergeArray(int[] a, int[] b, int[] c) {
    int x = 0;
    int y = 0;
    int flag = 0;//重复的次数
    while (x < a.length || y < b.length) {
        if (x > b.length) {
            c[x + y - flag] = b[y];
            y++;
        } else if (y > a.length) {
            c[x + y - flag] = a[x];
            x++;
        } else if (a[x] > b[y] ) {
            c[x + y - flag] = b[y];
            y++;
        } else if (a[x] < b[y] ) {
            c[x + y - flag] = a[x];
            x++;
        } else if (a[x] == b[y]) { //相等
            c[x + y - flag] = a[x];
            x++;
            flag++;
        }
    }
}