两个有序数组的合并问题

2020-04-22

总阅读量次

问题描述

编写函数，将两个有序 vector 数组合并成一个新的有序 vector数组，函数原型为：

1	vector<int> merg(vector<int> list1,vector<int> list2);

问题分析

第一步
将问题分解为两类处理方式：
两个有序数组是否都是不空；
两个有序数组的自身排列方式是升序还是降序；

第二步
在函数内先默认两个数组都为升序排列（包括数组为空，数组所有元素都相同两种情况）

第三步
把每种情况分别进行处理返回处理后的数组即可
设定这样的处理方式：
两个数组都为升序或者降序时，返回升序或者降序合并后的数组；
两个数组排列方式不同时（即一个为升序，一个为降序），返回降序排列后的数组；
有一个数组为空时，按照不为空的数组排列方式返回；
两个数组都为空时，输出“至少有一个数组不空”提示语句，返回一个空数组；

源代码

注：这里有很多代码十分冗余，只是为了满足题设，读者可改进为更简洁的执行方式

vector<int> merg(vector<int> list1,vector<int> list2){
	//分别取得两个数组的长度
    int length1 = list1.size();
    int length2 = list2.size();
    vector<int> relist(length1 + length2);
    int i(0);
    int j(0);
    int k(0);
    //默认两个数组都是升序排列
    int flag(0);
    bool flag1(true);
    bool flag2(true);
	//判断两个数组的排列方式
    while(length1 && flag < length1-1){
        if(list1[flag] > list1[flag +1]){
            flag1 = false;
            break;
        }
        flag++;
    }
    flag = 0;
    while(length2 && flag < length2-1){
        if(list2[flag] > list2[flag +1]){
            flag2 = false;
            break;
        }
        flag++;
    }

    //两个数组都为升序排列，输出为升序排列数组
    if(flag1 && flag2){
        while(j < length1 && k < length2){
            if(list1[j] <= list2[k])
                relist[i++] = list1[j++];
            else
                relist[i++] = list2[k++];
    }

    if(length1 && length2){
            if(j < length1)
                while(j < length1)
                relist[i++] = list1[j++];
            else
                while(k < length2)
                relist[i++] = list2[k++];
    }
    else if(!length1 && length2)
        relist = list2;
    else if(!length2 && length1)
        relist = list1;
    else
        cout << "请至少输入一个不为空的数组！";
    }

    //两个数组都为降序排列，输出为降序排列数组
    else if(!flag1 && !flag2){
        while(j < length1 && k < length2){
            if(list1[j] >= list2[k])
                relist[i++] = list1[j++];
            else
                relist[i++] = list2[k++];
    }

    if(length1 && length2){
            if(j < length1)
                while(j < length1)
                relist[i++] = list1[j++];
            else
                while(k < length2)
                relist[i++] = list2[k++];
    }
    else if(!length1 && length2)
        relist = list2;
    else if(!length2 && length1)
        relist = list1;
    else
        cout << "请至少输入一个不为空的数组！";
    }

    //两个数组不都为升序或者降序
    else{
            //数组1为升序且第二个数组不为空时，输出为降序数组
        if(flag1){
            vector<int> temp(length2);
            for(int m = 0,n = length2 -1;m < length2;m++,n--){
                temp[m] = list2[n];
            }
            while(j < length1 && k < length2){
            if(list1[j] <= temp[k])
                relist[i++] = list1[j++];
            else
                relist[i++] = temp[k++];
    }

    if(length1 && length2){
            if(j < length1)
                while(j < length1)
                relist[i++] = list1[j++];
            else
                while(k < length2)
                relist[i++] = temp[k++];
    }
    //若两个数组其中一个为空，则按照不为空的那个数组排列顺序输出
    else if(!length1 && length2)
        relist = list2;
    else if(!length2 && length1)
        relist = list1;
    else
        cout << "请至少输入一个不为空的数组！";
        }
        //数组2为升序且第二个数组不为空
    else{
           vector<int> temp(length1);
            for(int m = 0,n = length1 -1;m < length1;m++,n--){
                temp[m] = list1[n];
            }
            while(j < length1 && k < length2){
            if(temp[j] <= list2[k])
                relist[i++] = temp[j++];
            else
                relist[i++] = list2[k++];
    }

    if(length1 && length2){
            if(j < length1)
                while(j < length1)
                relist[i++] = temp[j++];
            else
                while(k < length2)
                relist[i++] = list2[k++];
    }
    else if(!length1 && length2)
        relist = list2;
    else if(!length2 && length1)
        relist = list1;
    else
        cout << "请至少输入一个不为空的数组！";
        }
    }
    return relist;
}

测试样例
(这里测试数组在主函数给出方便测试，故没有显示输入)

两个数组均为空
test 有一个数组为空
test
两个都为升序
test
两个都为降序
test
一个为升序一个为降序
test