【CT】LeetCode手撕—4. 寻找两个正序数组的中位数

题目

原题连接：4. 寻找两个正序数组的中位数

1- 思路

思路

将寻找中位数 ——> 寻找两个合并数组的第 K 大（K代表中位数）

实现

① 遍历两个数组 ：通过比较两个数组的第 [k/2] 个元素，如果 numsA[k/2] < numsB[k/2] 的时候，删除 numsA 的前半部分元素。
② 找剩余的 k/2 个元素

2- 实现

⭐4. 寻找两个正序数组的中位数——题解思路

在这里插入图片描述

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 定义 
        int n = nums1.length;
        int m = nums2.length;

        // 用来将 奇数长度 和 偶数长度合并
        int left = (n+m+1)/2;
        int right = (n+m+2)/2;
        return (getKth(nums1,0,n-1,nums2,0,m-1,left)+getKth(nums1,0,n-1,nums2,0,m-1,right))*0.5;
    }

    public int getKth(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
        int len1 = end1-start1+1;
        int len2 = end2-start2+1;
        // 始终让 len1 < len2
        if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);

        // 1. 递归终止条件
        if(len1 == 0 ) return nums2[start2+k-1];
        if(k==1) return Math.min(nums1[start1],nums2[start2]);

        // 2. 递归逻辑
        // 2.1 更新start用于递归：保证尽可能不越界 
        int i = start1 + Math.min(len1,k/2) -1;
        int j = start2 + Math.min(len2,k/2) -1;

        // 2.2 删除逻辑
        if(nums1[i] > nums2[j]){
            return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j - start2 + 1));
        }else{
            return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }
}

3- ACM 实现


public class midNum {
    public static double twoNumMid(int[] nums1,int[] nums2){
        int len1 = nums1.length;
        int len2 = nums2.length;

        int left = (len1+len2+1)/2;
        int right = (len1+len2+2)/2;

        return (getKth(nums1,0,len1-1,nums2,0,len2-1,left)+getKth(nums1,0,len1-1,nums2,0,len2-1,right))*0.5;
    }

    // 递归
    public static int getKth(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
        // 找len
        int len1 = end1-start1+1;
        int len2 = end2-start2+1;

        if(len1>len2) return getKth(nums2,start2,end2,nums1,start1,end1,k);

        // 2. 终止条件
        if(len1 == 0) return nums2[start2+k-1];
        if(k == 1) return Math.min(nums1[start1],nums2[start2]);

        // 3.单层递归
        int i = start1 + Math.min(k/2,len1)-1;
        int j = start2 + Math.min(k/2,len2)-1;

        // 删 nums2
        if(nums1[i]>nums2[j]){
            return getKth(nums1,start1,end1,nums2,j+1,end2,k-(j-start2+1));
        }else{
            return getKth(nums1,i+1,end1,nums2,start2,end2,k-(i-start1+1));
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("输入数组1的长度");
        int n = sc.nextInt();
        int[] nums1 = new int[n];
        System.out.println("输入数组1元素");
        for(int i = 0 ; i < n ; i ++){
            nums1[i] = sc.nextInt();
        }

        System.out.println("输入数组2的长度");
        int m = sc.nextInt();
        int[] nums2 = new int[m];
        System.out.println("输入数组2元素");
        for(int j = 0 ; j < m;j++){
            nums2[j] = sc.nextInt();
        }

        double res = twoNumMid(nums1,nums2);
        System.out.println("中位数是"+res);

    }
}