java 两个有序数组合并成一个有序数组算法

骑猪看日落 2024-04-19 16:08 29阅读 0赞

**1. 问题描述：**

对于两个有序数组arrayM，arrayN，长度分别为m和n；将这两个数组合并成一个数组并进行排序，要求时间复杂度为O（m+n）；

**2. 解题思路：**

1.  定义一个数组res，长度为m+n；
2.  定义两个index，分别为indexM、indexN，用来记录数组arrayM、arrayN的下标；
3.  通过分别遍历数组arrayM和arrayN的方式来比较每个值的大小，并将值存放到res中；
4.  判断indexM和indexN是否分别小于m、n，如果小于则继续执行，否则则表示有一个array遍历结束，需要单独对另一个array操作；
5.  具体代码如下：

//定义两个数组下标，遍历并记录index使用；
            int indexM =0;
            int indexN =0;
            int[] arrayM = new int[]{1,4,6,7,8};
            int[] arrayN = new int[]{2,3,5,9,11};
            //定义汇总数组的index；
            int k=0;
            //定义一个汇总数组
            int[] res = new int[arrayM.length+arrayN.length];
    
            //使用while循环遍历；当indexM或者indexN中有任意一个值为M或者N时，则表示当前某一个数组遍历到尾部
            while(indexM<arrayM.length&&indexN<arrayN.length){
                if (arrayM[indexM]<=arrayN[indexN]){
                    res[k]=arrayM[indexM];
                    indexM++;
                }else{
                    res[k]=arrayN[indexN];
                    indexN++;
                }
                k++;
            }
            // 判断哪一个数组被遍历到尾部，则此处将另一个数组添加到汇总数组中即可；
            // 此时 a =indexM，并a++,将M数组中剩余值添加到res中；
            if(indexM!=arrayM.length){
                for(int a = indexM ;a<arrayM.length;a++){
                    res[k]=arrayM[a];
                    k++;
                }
            }else{
                // 此时 a =indexM，并a++,将M数组中剩余值添加到res中；
                for(int a = indexN ;a<arrayN.length;a++){
                    res[k]=arrayN[a];
                    k++;
                }
            }
            for(int a =0;a<k;a++){
               System.out.println(res[a]);
           }

1.  最终输出结果如下：

1,2,3,4,5,6,7,8,9,11

问题二： 有一个service，该service中有两个synchronize方法，在controller中将该service注入，并在两个线程中执行分别调用这个service的不同方法，问：这两个方法该如何执行？  
解答：这两个方法会顺序执行；  
解释：synchronize为同步锁，该关键字修饰在方法上时表示对该对象加锁（对堆内该对象的地址加锁），且controller中不特殊说明，注入的service是单例的，所以在两个线程中分别调用该对象的不同方法时，只能有一个线程活的对象的锁，即同时只有一个线程可以执行；因此这两个方法虽然同时启动，但是只能顺序执行；