龙空技术网

刷题LeetCode:4.寻找两个正序数组的中位数

程序媛遇上处女座 259

前言:

如今朋友们对“数组求中位数算法”大约比较关切,你们都想要学习一些“数组求中位数算法”的相关知识。那么小编同时在网摘上收集了一些有关“数组求中位数算法””的相关内容,希望大家能喜欢,咱们一起来学习一下吧!

题目链接:

力扣

题目描述

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。

请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n))

题目分析

常规思路:

1.合并两个数组再排序,时间复杂度O(m+n),空间复杂度O(m+n)

2.归并排序,时间复杂度O(m+n),空间复杂度O(1)

本题解题思路应该如何呢?

根据题目中时间复杂度,可以考虑采用二分查找,这也是本题的难度所在。

假设两个有序数组分别是 A 和 B,两数组的总长度为 totalLength:

两数组总长度(totalLength)为奇数:中位数下标(midIndex)=totalLength/2,中位数=下标midIndex所在数;两数组总长度(totalLength)为偶数,中位数下标有两个 midIndex1,midIndex2, midIndex1=totalLength/2-1 ,midIndex2=totalLength/2,中位数=(下标midIndex1所在数+下标midIndex2所在数)/2;

注意:midIndex,为两数组合并后的下标,并不是真的将两个数组进行合并,大家要搞清楚这个概念。

这个时候,问题转化为找到数组 A 和 B 中的第 k 大元素(kElement),那怎么找到呢?

可以比较 A[k/2-1] 与B[k/2-1] :

A[k/2−1]<=B[k/2−1],则数组A中,下标为 0 至 k/2−1 的元素均小于kElement,可以排除这部分元素;A[k/2−1]>B[k/2−1],则数组B中,下标为 0 至 k/2−1 的元素均小于kElement,可以排除这部分元素;

很容易想到,查找范围缩小了一半,可以在排除后的新数组上继续进行二分查找,并且根据我们排除数的个数,减少 k 的值(因为我们排除的数都不大于第k 小的数)。需要注意以下几种情况:

1.保证数组不越界;

2.如果一个数组为空,说明该数组中的所有元素都被排除,我们可以直接返回另一个数组中第k小的元素;

3.若 k=1,只要返回两个数组首元素的最小值即可。

代码实现时间复杂度:O(log (m+n))空间复杂度:O(1)

public class FindMedianSortedArrays_4 {    /**     * 常规思路:     * 《1》合并两个数组在排序     * 《2》归并排序     *     * @param args     */    public static void main(String[] args) {        int[] num1 = {1, 3};        int[] num2 = {2};        //int[] num1 = {1, 3,4,9};        //int[] num2 = {1,2,3,4,5,6,7,8,9};        FindMedianSortedArrays_4 findMedianSortedArrays_4 = new FindMedianSortedArrays_4();        findMedianSortedArrays_4.findMedianSortedArrays(num1, num2);    }    /**     * 二分查找,巧妙     * 时间复杂度:O(log (m+n))     * 空间复杂度:O(1)     *     * @param nums1     * @param nums2     * @return     */    public double findMedianSortedArrays(int[] nums1, int[] nums2) {        int length1 = nums1.length;        int length2 = nums2.length;        int totalLength = length1 + length2;        // 两数组总长度(totalLength)为奇数,中位数下标(midIndex)=totalLength/2,中位数=下标k所在数        if (totalLength % 2 == 1) {            System.out.println("两数组总长度(totalLength)为奇数");            int midIndex = totalLength / 2;            double median = getKthElement(nums1, nums2, midIndex + 1);            System.out.println("median:" + median);            return median;        } else {            // 两数组总长度(totalLength)为偶数,中位数下标有两个 midIndex1,midIndex2, midIndex1=totalLength/2-1 ,midIndex2=totalLength/2,            // 中位数=(下标midIndex1所在数+下标midIndex2所在数)/2            System.out.println("两数组总长度(totalLength)为偶数");            int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;            double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;            System.out.println("median:" + median);            return median;        }    }    /**     * 获取第k小的元素     *     * @param nums1     * @param nums2     * @param k     * @return     */    public int getKthElement(int[] nums1, int[] nums2, int k) {        System.out.println("初始k:" + k);        int length1 = nums1.length;        int length2 = nums2.length;        // 用来记录两个数组寻找第k小元素的起始下标        int index1 = 0, index2 = 0;        while (true) {            // 边界情况,数组1为空,只需要考虑数组2            if (index1 == length1) {                return nums2[index2 + k - 1];            }            // 边界情况,数组2为空,只需要考虑数组1            if (index2 == length2) {                return nums1[index1 + k - 1];            }            if (k == 1) {                return Math.min(nums1[index1], nums2[index2]);            }            // 比较 num1[k/2-1] 与 num1[k/2-1]            int compareIndex1 = Math.min(index1 + k / 2, length1) - 1;            int compare1 = nums1[compareIndex1];            int compareIndex2 = Math.min(index2 + k / 2, length2) - 1;            int compare2 = nums2[compareIndex2];            if (compare1 < compare2) {                k -= compareIndex1 - index1 + 1;                index1 = compareIndex1 + 1;            } else {                k -= compareIndex2 - index2 + 1;                index2 = compareIndex2 + 1;            }            System.out.println("compare1:" + compare1);            System.out.println("compare2:" + compare2);            System.out.println("index1:" + index1);            System.out.println("index2:" + index2);            System.out.println("k:" + k);        }    }}

注意:while语句中是最核心的部分,也就是二分查找的主要思想。

好了,今天就到这里,感谢各位看官到这里,不如点个关注吧!

标签: #数组求中位数算法 #数组 中位数