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

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

1- 思路

题目识别

• 识别1 ：给定两个数组 nums1 和 nums2 ，找出数组的中位数

二分

思路

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

实现

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

其实现思路在于，始终让 nums1 为元素数量少的数组

2- 实现

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

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 1. 长度
        int len1 = nums1.length;
        int len2 = nums2.length;

        // 定义 right
        // 排除奇、偶 影响
        int left = (len1+len2+1)/2;
        int right = (len1+len2+2)/2;
        return ((findK(nums1,0,len1-1,nums2,0,len2-1,left) + findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);
    }

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

        // 判断
        if(len1==0) return nums2[start2+k-1];
        if(k == 1) return Math.min(nums1[start1],nums2[start2]);

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

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

    }
}

3- ACM 实现

public class findM {

    public static double findMid(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 ((findK(nums1,0,len1-1,nums2,0,len2-1,left) + findK(nums1,0,len1-1,nums2,0,len2-1,right))*0.5);
    }


    private static double findK(int[] nums1,int start1,int end1,int[] nums2,int start2,int end2,int k){
        // 递归终止
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if(len1>len2) return findK(nums2,start2,end2,nums1,start1,end1,k);

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

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


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

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String input = sc.nextLine();
        input = input.replace("[","").replace("]","");

        String input2 = sc.nextLine();
        input2 = input2.replace("[","").replace("]","");

        String[] parts = input.split(",");
        int[] nums = new int[parts.length];
        for(int i = 0 ; i < nums.length;i++){
            nums[i] = Integer.parseInt(parts[i]);
        }

        String[] parts2 = input2.split(",");
        int[] nums2 = new int[parts.length];
        for(int i = 0 ; i < nums2.length;i++){
            nums2[i] = Integer.parseInt(parts2[i]);
        }

        System.out.println("结果是"+findMid(nums,nums2));

    }
}