04.寻找两个有序数组的中位数(难度:困难)

04.寻找两个有序数组的中位数(难度:困难)

题目描述

给定两个大小为 m 和 n 的有序数组 nums1nums2

请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

解法一:

这道题是求两个有序数组的中位数,如果不限制时间复杂度的话,那么这道题将会无比简单。

把长度为m和长度为n的两个数组的数据放在一个新的数组中,然后对数组进行排序,找到中位数。

找中位数的时候,因为组合后的数组元素个数(m + n)的奇偶性不确定,如果是奇数的话,那么中位数就是第(m+n)/ 2 个元素,如果是偶数的话,那么中位数就是第(m + n )/ 2 个元素和第(m + n)/ 2 + 1个。

我们可以利用int整型向下取整的特点,把上面两种情况归结为一种通用的解法,我们可以找到下标(m + n - 1)/ 2和下标(m + n )/ 2元素,然后求两数的平均值。

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int [] result = Arrays.copyOf(nums1, nums1.length + nums2.length);
        
        /**将一个数组片段复制到另一个数组的指定位置
         * System.arraycopy(src, srcPos, dest, destPos, length)
         * src: 源数组
         * srcPos: 从源数组复制数据的起始位置
         * dest: 目标数组
         * destPos: 复制到目标数组的起始位置
         * length: 复制的长度
         */
        System.arraycopy(nums2, 0, result, nums1.length, nums2.length);     
        Arrays.sort(result);
        double d = (double)(result[(nums1.length + nums2.length -1)/2] + result[(nums1.length + nums2.length )/2])/2;
        
        return d;
    }

执行用时 :4 ms, 在所有 Java 提交中击败了31.34%的用户

内存消耗 :42.2 MB, 在所有 Java 提交中击败了96.67%的用户

上述的关键代码虽然只有4行,但是在时间复杂度上是不满足题目要求的

解法二:

看见时间复杂度的限制O(log(m+n)),肯定要用二分查找法来解决,其次,中位数的应在的位置依旧按照解法一的方法,不过这次我们不合并数组了,这样会增加时间复杂度。

找中位数的时候,因为两个数组的元素个数之和(m + n)的奇偶性不确定,如果是奇数的话,那么中位数就是第(m+n)/ 2 个元素,如果是偶数的话,那么中位数就是第(m + n +1 )/ 2 个元素和第(m + n +2)/ 2 个。

下来我们着重看看,如何在两个有序数组中找到第k个元素:

首先,我们利用i和j分别标记数组nums1和 nums2的起始位置,

此次我们处理一些边界问题:

(1)当一个数组的起始位置大于等于该数组的长度,表明该数组所有的数字都已经被淘汰了,相当于空数组,那么我们只需要继续在另一个数组里面找,直接可以找出来。

(2)当k = 1的时候,我们只需要比较两个有序数组的起始位置i和j 的数字就好。

难点在于如何处理一般情况?

为了加快搜索速度,我们使用二分法:

(1)我们可以先对k二分,意思就是去找到nums1和nums2的第k/2个数字。

(2)因为两个数字的长度不定,所有我们需要先判断一下两个数组是否都含有第k/2个数字,如果存在就取出来,如果不存在就给它赋一个最大值,赋最大值的原因是:我们后面会通过比较两个数组中取出来的数字,如果小的那个数组,那么前k/2个元素里面必然不会有中位数,那么我们就可以把它舍去。

(3)那么会不会两个数组都不存在第k/2个元素,在这道题里面是不可能的,因为k是m+n的中间值,所以至少也会有一个数组中有第k/2个元素。

(4)最后就是二分法的核心,而是递归的重点。我们比较两个数组的第k/2小的元素值mid1和mid2,如果nums1的mid1小的话,那么说明中位数肯定不住nums1数组的前k/2中,我们就可以把第一个数组的前k/2个数字淘汰,将nums1的起始位置i向后移动k/2个,并且让k也减去k/2,调用递归。反之,如果是nums2的mid2小的话,那么我们就淘汰nums2的前k/2个元素,并且让k减去k/2,调用递归。

    /**
     * 第二种解法:二分查找法
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0;
    }

    /**
     * 在nums1和nums2中找出第k小的元素
     * 
     * @param nums1 nums1数组
     * @param i     nums1数组的起始位置
     * @param nums2 nums2数组
     * @param j     nums2数组的起始位置
     * @param k     需要找到的元素的序号
     * @return 第k小的元素值
     */
    public static int find(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length)
            return nums2[j + k - 1]; // nums1数组全部被舍弃
        if (j >= nums2.length)
            return nums1[i + k - 1]; // nums2数组全部被舍弃
        // 当k = 1 的时候,两个数组的布局基本相同,最后只需要找到
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }

        /*
         * 分别找到两个数组中的第k/2位置的元素,如果不存在就给他赋最大值, 比较两个值,值小的数组则淘汰其前k/2个元素 最后把k也减去k/2,继续递归
         */
        int mid1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (mid1 < mid2) {
            return find(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return find(nums1, i, nums2, j + k / 2, k - k / 2);
        }

    }

测试类

package com.company.project.hot100;

import java.util.Arrays;

/**
 * 4. 寻找两个有序数组的中位数 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
 * 
 * 请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
 * 
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * 
 * 示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0
 * 
 * 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5
 * 
 * @author God_86
 *
 */
public class Question04 {
    /**
     * 第一种解法:合并数组排序,找到中位数
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] result = Arrays.copyOf(nums1, nums1.length + nums2.length);

        /**
         * 将一个数组片段复制到另一个数组的指定位置 System.arraycopy(src, srcPos, dest, destPos, length)
         * src: 源数组 srcPos: 从源数组复制数据的起始位置 dest: 目标数组 destPos: 复制到目标数组的起始位置 length: 复制的长度
         */
        System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
        Arrays.sort(result);
        double d = (double) (result[(nums1.length + nums2.length - 1) / 2] + result[(nums1.length + nums2.length) / 2])
                / 2;

        return d;
    }

    /**
     * 第二种解法:和第一种一样,不过利用位运算,可以优化计算
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        if (nums1.length < 2 && nums2.length < 2) {
            if (nums1.length == 0) {
                return (double) nums2[0];
            } else if (nums2.length == 0) {
                return (double) nums1[0];
            }
            return (double) (nums1[0] + nums2[0]) / 2;
        }
        int[] result = Arrays.copyOf(nums1, nums1.length + nums2.length);
        /**
         * 将一个数组片段复制到另一个数组的指定位置 System.arraycopy(src, srcPos, dest, destPos, length)
         * src: 源数组 srcPos: 从源数组复制数据的起始位置 dest: 目标数组 destPos: 复制到目标数组的起始位置 length: 复制的长度
         */
        System.arraycopy(nums2, 0, result, nums1.length, nums2.length);
        Arrays.sort(result);
        int mid = result.length >> 1;
        if ((result.length & 1) == 1) {
            return (double) result[(result.length - 1) >> 1];
        } else {
            return (double) (result[mid - 1] + result[mid]) / 2;
        }
    }

    /**
     * 第三种解法:二分查找法
     * 
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays3(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (find(nums1, 0, nums2, 0, left) + find(nums1, 0, nums2, 0, right)) / 2.0;
    }

    /**
     * 在nums1和nums2中找出第k小的元素
     * 
     * @param nums1 nums1数组
     * @param i     nums1数组的起始位置
     * @param nums2 nums2数组
     * @param j     nums2数组的起始位置
     * @param k     需要找到的元素的序号
     * @return 第k小的元素值
     */
    public static int find(int[] nums1, int i, int[] nums2, int j, int k) {
        if (i >= nums1.length)
            return nums2[j + k - 1]; // nums1数组全部被舍弃
        if (j >= nums2.length)
            return nums1[i + k - 1]; // nums2数组全部被舍弃
        // 当k = 1 的时候,两个数组的布局基本相同,最后只需要找到
        if (k == 1) {
            return Math.min(nums1[i], nums2[j]);
        }

        /*
         * 分别找到两个数组中的第k/2位置的元素,如果不存在就给他赋最大值, 比较两个值,值小的数组则淘汰其前k/2个元素 最后把k也减去k/2,继续递归
         */
        int mid1 = (i + k / 2 - 1 < nums1.length) ? nums1[i + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = (j + k / 2 - 1 < nums2.length) ? nums2[j + k / 2 - 1] : Integer.MAX_VALUE;
        if (mid1 < mid2) {
            return find(nums1, i + k / 2, nums2, j, k - k / 2);
        } else {
            return find(nums1, i, nums2, j + k / 2, k - k / 2);
        }

    }

    public static void main(String[] args) {
        int[] nums1 = { 9, 10, 11, 12, 13, 14 };
        int[] nums2 = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 };
//      int[] nums1 = { 1 };
//      int[] nums2 = { 2 };

        System.out.println(findMedianSortedArrays3(nums1, nums2));

    }
}

版权声明:
作者:玉兰
链接:https://www.techfm.club/p/43525.html
来源:TechFM
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>