回 帖 发 新 帖 刷新版面

主题:合并两个数组的算法

已知数组R1[5] R2[5] 按升序排列,用算法实现将R1[5] R2[5] 合在一起后升序排列


下面我写的算法  不知道错在哪里。调试了,不晓得是什么原因第一个for循环4次就终止了

public static int[] p(int r1[],int r2[]){

     int R[] = new int[r1.length+r2.length];
     int a=0;
     int p=0;
     for(int i=0;i<r1.length;i++){
         for(int j=p;j<r2.length;j++){
            if(r1[i]<r2[j]){
                R[a] = r1[i];
                a++;
                break;
            }else{
                R[a] = r2[j];
                p = j+1;
                a++;
            }
         }
     }
     return R;
 }

回复列表 (共3个回复)

沙发

你好。
如果r2的最后一个值比r1的最后一个值大的话,r2的最后一个值就取不到了。
所以在for循环之前,先判断一下r1,r2的最后一个值得大小,大的作为r1小的作为r2就可以了。
当然还有其他的方法,在这里就不多说了。
加油。

板凳

不好意思。刚刚没说对。
在刚刚判断最大值在r1还是r2之后,打的作为r1,小的作为r2.
在里面一个for循环后面加上   if(p>=r2.length){
                    R[a] = r1[i];
                    a++;
                     }
把r1多出来的部分写道R中去。

3 楼

我重新写了一个,你看下。这个效率更高一点复杂度为两个数组长度和
   public static int[] p(int r1[], int r2[]) {
        int[] result = new int[r1.length + r2.length];
        int i1 = 0;
        int i2 = 0;
        int c = 0;
        //两个数组同步扫描
        while (i1 < r1.length && i2 < r2.length) {
            if (r1[i1] < r2[i2]) {
                result[c++] = r1[i1];
                i1++;
            } else if (r1[i1] == r2[i2]) {
                result[c++] = r1[i1];
                i1++;
                i2++;
            } else {
                result[c++] = r2[i2];
                i2++;
            }
        }
        //对剩余部分进行处理
        if(i1==r1.length)
        {
            for(int j=i2;j<r2.length;j++)
                result[c++]=r2[j];
        }
        if(i2==r2.length)
        {
            for(int j=i1;j<r1.length;j++)
                result[c++]=r1[j];
        }
        return result;
    }

我来回复

您尚未登录,请登录后再回复。点此登录或注册