编程题：在两个长度相等的排序数组中找到上中位数（递归练习）

心已赠人 2023-05-21 15:11 105阅读 0赞

### 文章目录 ###

*   *  问题描述：
     *  解题思路：
     *   *  思路1：暴力解法
         *  思路2：思路1的改装版
         *  思路3：递归版
         *  思路4：思路3的改装，迭代版
     *  解题代码：
     *   *  思路1代码
         *  思路2代码
         *  思路3代码
         *  思路4代码
         *  LeetCode解题代码（用的思路2）

链接1： [牛客网传送门][Link 1]  
链接2： [LeetCode传送门][LeetCode]

## 问题描述： ##

这里的问题描述是牛客网的，LeetCode上请自己点击链接进行查看，LeetCode的不同之处是两个原始的数组的长度可能不同。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]

## 解题思路： ##

### 思路1：暴力解法 ###

观察题我们可以得到：就是有两个有序的数组，然后把他们合并起来时求出这一串数据的中位数。  
既然是求新组合数据的中位数，那么我们可以将这两个数组合并为一个数组，然后重新排序，找出要求的中位数就好了。

### 思路2：思路1的改装版 ###

同样是将这两个数组合并为一个数组，然后重新排序的思路（思路1是全部数据放进去排序，这里我们可以实现进行排序然后在放进新数组），这样我们就可以不用快排的递归：

1.  arr1\[0\]和arr2\[0\]比较，选出较小的放在新数组的arr\[0\]。
2.  假如上边是arr1\[0\]>arr2\[0\],将arr2\[0\]赋值到arr\[0\]后，我们将进行arr1\[0\]和arr2\[1\]的比较，再次选出小的放进新数组中。
3.  如此循环2步骤，肯定会有一个数组会先遍历完，然后我们将另一个数组未遍历的元素放进新数组就好了。
4.  这样新数组的所有数据在放进后就是有序的，我们直接选中位数返回即可。

### 思路3：递归版 ###

题上说两个数组事先就是有序的，那个请往下看：  
举例1，比如两个数组是这样的：  
**当两个数组的长度为偶数时：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]  
分别选出这两个数组的上中位数的下标，即

mid1 = (n-1)/2 = 1  
mid2 = (n - 1)/2 = 1

*  假如 arr2\[mid2\] > arr1\[mid1\]，那么我们要找的目标数是一定存在于 arr1\[mid1+1…n\] 和 arr2\[0…mid2\]中，而不可能存在于 arr1\[0…mid1\] 和 arr2\[mid2+1…n\] 之中，也就是说，我们接下来只需要在arr1\[mid1+1…n\] 和 arr2\[0…mid2\] 中查找就行了。

举例2，比如两个数组是这样的：  
**当两个数组的长度为奇数时：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]  
分别选出这两个数组的上中位数的下标，即

mid1 = (n-1)/2 = 2  
mid2 = (n - 1)/2 = 2

*  这个时候如果 arr2\[mid2\] > arr1\[mid1\] 时，则和上面那个情况有点小差别，这时候目标数只存在于 arr1\[mid1…n\] 和 arr2\[0…mid2\]中。
 *  注意他们的差别，从arr1\[mid1+1…n\] => arr1\[mid1…n\]。

### 思路4：思路3的改装，迭代版 ###

理解了思路3的原理后，由于递归会不停的调用栈（直到出口），所以我们可以将其代码改编为迭代版的。

## 解题代码： ##

### 思路1代码 ###

import java.util.Scanner;
    public class Main { 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                //开辟一个新数组来存放以前两个数组的数据，数组大小是他两之和
                int[] arr=new int[2*n];
                int[] arr1=new int[n];
                int[] arr2=new int[n];
                int j=0;
                 for(int i=0;i<arr1.length;i++){ 
                     arr1[i]=sc.nextInt();
                   //在输入arr1数据的同时对arr的数组也进行赋值
                     arr[j]=arr1[i];
                     j++;
                }
                 for(int i=0;i<arr2.length;i++){ 
                    arr2[i]=sc.nextInt();
                     //在输入arr2数据的同时对arr的数组也进行赋值
                     arr[j]=arr2[i];
                     j++;
                }
                quickSort(arr); //开始快速排序
                //题上说要求的是具体的数，这里我们是根据它的下标返回的
                if(arr.length%2==0){ 
                    System.out.println(arr[n-1]);  //本来是n,下标要减1，所以是n-1
                }else{ 
                    System.out.println(arr[n/2]);//本来是n/2+1,下标要减1，所以是n/2
                }
            }
        }
        public static void quickSort(int[] arr){ 
            quick(arr,0,arr.length-1);
        }
        public static void quick(int[] arr,int low,int high){ 
            if(low==high){ 
              return;
            }
            int par=partion(arr,low,high);
            if(par>low+1){ 
              quick(arr,low,par-1);
            }
            if(par+1<high){ 
              quick(arr,par+1,high);
            }
        }
         public static int partion(int[] arr,int low,int high){ 
            int temp=arr[low];
            while(low<high){ 
            while((low<high)&&arr[high]>=temp){ 
                high--;
              }
               if(low==high){ 
                   break;
               }else{ 
                   arr[low]=arr[high];
               }
            while((low<high)&&arr[low]<=temp){ 
                low++;
            }
               if(low==high){ 
                  break;
               }else{ 
                  arr[high]=arr[low];
               }
               }
            arr[low]=temp;
            return low;
        }
    }

### 思路2代码 ###

import java.util.Scanner;
    public class Main { 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                int[] arr=new int[2*n];
                int[] arr1=new int[n];
                int[] arr2=new int[n];
     
                for(int i=0;i<arr1.length;i++){ 
                    arr1[i]=sc.nextInt();
                }
                for(int i=0;i<arr2.length;i++){ 
                    arr2[i]=sc.nextInt();
                }
     
                int x=0; //arr的指针（这样就知道新插进来的元素往哪放）
                int j=0;//对arr1遍历的指针
                int p=0;//对arr2遍历的指针
                while(j<n&&p<n){  //循环的出口是任意一个数组遍历完
                    if(arr1[j]<=arr2[p]){ 
                    //小的放进新数组后继续小的元素的下一个元素和刚刚较大的对比
                        arr[x]=arr1[j];
                        j++;
                    }else{ 
                        arr[x]=arr2[p];
                        p++;
                    }
                    x++; //放进新数组一个元素后，下次放到插入元素的后边
                }
                if(j==n){  //说明arr2没有遍历完
                    for(;x<arr.length;x++){ 
                        arr[x]=arr2[p++]; //把arr2剩下的元素搬到新数组中
                    }
                }
                if(p==n){  //同上
                    for(;x<arr.length;x++){ 
                        arr[x]=arr2[j++];
                    }
                }
                //按照题上的要求进行返回
                if(arr.length%2==0){ 
                    System.out.println(arr[n-1]);
                }else{ 
                    System.out.println(arr[n/2]);
                }
            }
        }
     
    }

### 思路3代码 ###

import java.util.Scanner;
    public class Main { 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                int[] arr1=new int[n];
                int[] arr2=new int[n];
                 for(int i=0;i<arr1.length;i++){ 
                   arr1[i]=sc.nextInt();
                }
                 for(int i=0;i<arr2.length;i++){ 
                   arr2[i]=sc.nextInt();
                }
                System.out.println(getUpMedian(arr1,arr2));
            }
        }
        private static int getUpMedian(int[] arr1,int[] arr2){ 
            //开始寻找 
            return find(arr1,0,arr1.length-1,arr2,0,arr2.length-1);
        }
        //l1代表下一次在arr1寻找的起始下标，r1是终止下标
        //l2,r2同上
        private static int find(int[] arr1,int l1,int r1,int[] arr2,int l2,int r2){ 
            //计算得出每次的mid1,mid2，计算的时候前边加的l1,l2是加上相比上一次下标的的偏移量
            int mid1=l1+(r1-l1)/2;
            int mid2=l2+(r2-l2)/2;
            //当数组中只剩一个数的时候，把两个数组中较小的数返回
            //假如arr1={1},arr2={2};排序后是1 2，我们应该返回1
            if(l1>=r1||l2>=r2){ 
                return Math.min(arr1[l1],arr2[l2]);
            }
            //元素个数为奇数时，offset(偏移量)为0；为偶数时offset为1
            int offset=((r1-l1+1)&1)^1;
            if(arr1[mid1]<arr2[mid2]){ 
                return find(arr1,mid1+offset,r1,arr2,l2,mid2);
            }else if(arr1[mid1]>arr2[mid2]){ 
                return find(arr1,l1,mid1,arr2,mid2+offset,r2);
            }else{  //arr1[mid1]==arr2[mid2]
                return arr1[mid1];// 返回 arr2[mid2]也可以
            }
        }
    }

### 思路4代码 ###

import java.util.Scanner;
    public class Main { 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                int n=sc.nextInt();
                int[] arr1=new int[n];
                int[] arr2=new int[n];
                 for(int i=0;i<arr1.length;i++){ 
                   arr1[i]=sc.nextInt();
                }
                 for(int i=0;i<arr2.length;i++){ 
                   arr2[i]=sc.nextInt();
                }
                System.out.println(getUpMedian2(arr1,arr2));
            }
        }
        private static int getUpMedian2(int[] arr1, int[] arr2) { 
            if(arr1==null||arr2==null){ 
                return -1;
            }
            int l1=0;
            int r1=arr1.length-1;
            int l2=0;
            int r2=arr2.length-1;
            int mid1=0;
            int mid2=0;
            int offset=0;
            while(l1<r1&&l2<r2){ 
                mid1=l1+(r1-l1)/2;
                mid2=l2+(r2-l2)/2;
                offset=((r1-l1+1)&1)^1;
                 if (arr1[mid1] < arr2[mid2]) { 
                     l1=mid1+offset;
                     r2=mid2;
                 } else if (arr1[mid1] > arr2[mid2]) { 
                     r1=mid1;
                     l2=mid2+offset;
                 } else { 
                     return arr1[mid1];// 返回 arr2[mid2]也可以
                 }
            }
            return Math.min(arr1[l1],arr2[l2]);
        }
    }

### LeetCode解题代码（用的思路2） ###

class Solution { 
        public double findMedianSortedArrays(int[] arr1, int[] arr2) { 
            int n=arr1.length;
            int m=arr2.length;
             int[] arr=new int[arr1.length+arr2.length];
                int x=0; //arr的指针（这样就知道新插进来的元素往哪放）
                int j=0;//对arr1遍历的指针
                int p=0;//对arr2遍历的指针
                while(j<n&&p<m){  //循环的出口是任意一个数组遍历完
                    if(arr1[j]<=arr2[p]){ 
                    //小的放进新数组后继续小的元素的下一个元素和刚刚较大的对比
                        arr[x]=arr1[j];
                        j++;
                    }else{ 
                        arr[x]=arr2[p];
                        p++;
                    }
                    x++; //放进新数组一个元素后，下次放到插入元素的后边
                }
                if(j==n){  //说明arr2没有遍历完
                    for(;x<arr.length;x++){ 
                        arr[x]=arr2[p++]; //把arr2剩下的元素搬到新数组中
                    }
                }
                if(p==m){  //同上
                    for(;x<arr.length;x++){ 
                        arr[x]=arr1[j++];
                    }
                }
                //按照题上的要求进行返回
                if(arr.length%2==0){ 
                    return (double) (arr[arr.length/2]+arr[arr.length/2-1])/2;
                    
                }else{ 
                     return (double) arr[arr.length/2];
                }
       
        }
        
    }

[Link 1]: https://www.nowcoder.com/questionTerminal/08588d568e164e0a9958b5d6a3c351f5?orderByHotValue=1&questionTypes=000100&mutiTagIds=3446&page=1&onlyReference=false
[LeetCode]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70]: /images/20230521/3ca5f35589d74afb8aea676678f5e825.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 1]: /images/20230521/18f1353da291463d998adce5eff50343.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0ODQwMTQ4_size_16_color_FFFFFF_t_70 2]: /images/20230521/2b8e80acb29b4ae39f2fe9e19e7f6565.png