算法 2.4 归并排序 + 二分查找：寻找两个正序数组的中位数【

2021-01-30  本文已影响0人  珺王不早朝

题目描述

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2
请你找出这两个正序数组的中位数

进阶：你能设计一个时间复杂度为 O(log(m + n)) 的算法解决此问题吗？

提示：
• 0 <= m、n <= 1000
• m+n >= 1
• -106 <= nums1[i] 、nums2[i] <= 106

输入：nums1 = [1, 3]，nums2 = [2]
输出：2.0
解释：合并数组=[1,2,3]，因此中位数是 2

输入：nums1 = [1, 2]，nums2 = [3, 4]
输出：2.5
解释：合并数组=[1,2,3,4]，因此中位数是 (2 + 3)/2 = 2.5

数据结构

算法思维

关键知识点：归并排序（Merge Sort）

  首先将数组拆分成两部分
  对这两部分分别递归排序
  元素个数大于1，继续拆分
  只有一个元素时无需排序，结束递归
  在对有序数组进行两两合并

class Solution{
    public static int[] mergeSort(int[] arr) {
        if (arr.length < 2) return arr;
        //计算中间位置
        int mid = arr.length / 2;
        //分解为左右两部分,分别排序
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        left = mergeSort(left);
        int[] right=Arrays.copyOfRange(arr,mid,arr.length);
        right = mergeSort(right);
        //合并两个排序后的数组为一个数组
        return merge(left, right);
    }

    private static int[] merge(int[] l, int[] r) {
        int[] result = new int[l.length + r.length];
        int lIndex = 0;
        int rIndex = 0;
        for (int i = 0; i < result.length; i++) {
            if (lIndex < l.length && rIndex < r.length) {
                if (l[lIndex] <= r[rIndex]) {
                    result[i] = l[lIndex++];
                } else {
                    result[i] = r[rIndex++];
                }
            } else if (lIndex >= l.length) {
                result[i] = r[rIndex++];
            } else {
                result[i] = l[lIndex++];
            }
        }
        return result;
    }
}

时间复杂度：O(nlogn)
  • 需要递归的将数组切割 logn 次，然后进行两两归并，时间复杂度为 O(nlogn)

空间复杂度：O(n)
  • 递归深度是 O(logn)
  • 每次递归在合并时需额外辅助空间，长度与待排序的数组长度相等
  • 每次递归都会释放掉所占的辅助空间，最大辅助空间为 O(n)
  • 所以空间复杂度为 O(n+logn) = O(n)

关键知识点：二分查找（折半查找）

使用折半的方式在有序数组中查找某一特定元素

每一次比较都使查找范围缩小一半

//二分查找算法，在a[start] ~ a[end]中查找key
public int binarySearch(int key, int a[], int start, int end) {
    if (start > end) //未找到key，返回-1
        return -1;

    int m = (start + end) / 2;
    if (a[m] == key) //找到key，返回key的id
        return m;
    if (a[m] > key)
        return binarySearch(key, a, start, m - 1);//在m左侧继续查找
    
    return binarySearch(key, a, m + 1, end);//在m右侧继续查找
}

解题步骤

一. Comprehend 理解题意
寻找两个数组的中位数
进阶要求
宽松限制
细节问题
二. Choose 选择数据结构与算法
数据结构选择
算法思维选择
算法思维优化
三. Code 编码实现基本解法
解题思路剖析
代码实现
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        
        //定义指针p1,p2 分别指代nums1和nums2的当前元素
        int p1 = 0, p2 = 0;
        //定义中位数m1和m2，指代当前第i-1大的数和第i大的数
        int m1 = 0, m2 = 0;
        
        for (int i = 0; i <= (m + n) / 2; i++) {
            m1 = m2; //指针右移
            //若nums1未处理完，并且 nums2已处理完 或 p1元素小于p2元素
            //则第i大的元素为nums1当前元素
            if (p1 < m && (p2 >= n || nums1[p1] < nums2[p2])) {
                m2 = nums1[p1++];
            } else { //否则第i大的元素为nums2当前元素
                m2 = nums2[p2++];
            } 
        }

        //若m+n为奇数，返回m2，若m+n为偶数，返回(m1+m2)/2.0
        if (((m + n) % 2) == 0) return (m1 + m2) / 2.0;
        else return m2;
    }
}

时间复杂度：O(m+n)
  • 需要多次比较两个数组中元素的大小
  • 只需要找到中间位置的元素，并不需要完成整个归并，总的比较次数为 (m+n)/2 + 1
  • 时间复杂度为 O(m+n)

空间复杂度：O(1)
  • 常数级的变量空间 O(1)

执行耗时：3 ms，击败了 69.10% 的Java用户
内存消耗：41 MB，击败了 24.82% 的Java用户

四. Consider 思考更优解
剔除无效代码 优化空间消耗
寻找更好的算法思维
中位数的性质
五. Code 编码实现最优解
解题思路剖析
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        //较短的数组在前，确保m <= n
        if (m > n) return findMedianSortedArrays(nums2, nums1);

        //定义p、q为nums1分界线范围，共m+1个可能的划分位置
        int p = 0, q = m;
        int i = 0, j = 0; //nums1、num2的分界位置

        //使用循环代替递归，减少空间消耗
        while (p <= q) {
            i = (p + q) / 2; //二分确定nums1当前分界位置
            //根据i确定nums2的分界位置，使得左侧元素数-右侧元素数为0或1
            j = (m + n + 1) / 2 - i;
            //nums1右侧最小值小于nums2左侧最大值，nums1划分位置在[i+1, q]之间
            if (j != 0 && i != m && nums1[i] < nums2[j - 1]) p = i + 1;
            //nums1左侧最大值大于nums2右侧最小值，nums1划分位置在[p, i-1]之间
            else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) q = i - 1;
            //当前划分位置左侧的最大值小于右侧的最小值，满足要求
            else break;
        }

        //m+n为奇数，返回左侧的最大值 左侧最大值：三种情况 nums1为空、nums2为空、都不为空
        int maxLeft = i == 0 ? nums2[j - 1] : (j == 0 ? nums1[i - 1] : Math.max(nums1[i - 1], nums2[j - 1]));
        if ((m + n) % 2 == 1) return maxLeft;

        //m+n为偶数，返回左侧最大值与右侧最小值的平均 右侧最小值：三种情况 nums1为空、nums2为空、都不为空
        int minRight = i == m ? nums2[j] : (j == n ? nums1[i] : Math.min(nums1[i], nums2[j]));
        return (maxLeft + minRight) / 2.0;
    }
}

时间复杂度：O(log(min(m,n)))
  • 只需要对 nums1 和 nums2 中较短数组进行二分查找
  • 二分查找的时间复杂度为 O(log(min(m,n)))

空间复杂度：O(1)
  • 常数级内存空间 O(1)

执行耗时：2 ms，击败了 100.00% 的Java用户
内存消耗：40.9 MB，击败了 35.53% 的Java用户

六. Change 变形与延伸
题目变形
延伸扩展
上一篇 下一篇

猜你喜欢

热点阅读