Leetcode算法系列| 4. 寻找两个正序数组的中位数

发布时间:2023年12月23日

1.题目

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n))

  • 示例1:
输入:nums1 = [1,3], nums2 = [2]
输出:2.00000
解释:合并数组 = [1,2,3] ,中位数 2
  • 示例 2:
输入:nums1 = [1,2], nums2 = [3,4]
输出:2.50000
解释:合并数组 = [1,2,3,4] ,中位数 (2 + 3) / 2 = 2.5
  • 提示:
    • nums1.length == m
    • snums2.length == n
    • 0 <= m <= 1000
    • 0 <= n <= 1000
    • 1 <= m + n <= 2000
    • -10^6 <= nums1[i], nums2[i] <= 10^6

2.题解

C# 解法一:合并List根据长度找中位数

  • 提new 一个 List , 并将 nums1 和 nums2 都添加到list 中,然后进行排序。对于排序后的 list, 根据长度计算出中位数的index,进而计算出最终结果。假设合并后的list长度为13,则从小到大第7个数字为中位数,resultIndex=6;假设合并后的list长度为14,则从小到大第7,8个数字的平均值为中位数,index 分别为 6,7,此时resultIndex =7,resultIndex-1 =6 , 结果为 ( list[resultIndex-1] + list[resultIndex] ) / 2.0 ;
public class Solution {
     public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;
        List<int> list = new List<int>(nums1);
        list.AddRange(nums2);
        list.Sort();
        if (len % 2 == 0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            return list[resultIndex];
        }
    }
}

1

  • 时间复杂度:O( (m+n)(1+log(m+n) ))
    • 将长度为m,n的两个数组添加到list,复杂度分别为常数级的m和n ;list.Sort()的复杂度根据官方文档可得为 (m+n)log(m+n),所以该方法时间复杂度为 O( m+n+(m+n)log(m+n) ) = O( (m+n)(1+log(m+n) ))
  • 空间复杂度:O(m+n)
    • 使用list的长度为m+n.

C# 解法二:归并排序后根据长度找中位数

  • 方法一使用了list.Sort() 方法,可以对list进行排序,但是,若题目给出的nums1 和 nums2 是无序数组,使用 list.Sort() 才算是 物有所用。 本题中 nums1 和 nums2 是有序数组,所以使用 list.Sort() 有写 杀鸡用宰牛刀的感觉,换句话说,这里面存在着效率的浪费。我们可以利用 【nums1 和 nums2 是有序数组】 这个条件,来精简我们的排序。
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        // nums1 与 nums2 有序添加到list中
        List<int> list = new List<int>();
        int i = 0, j = 0;
        int m = nums1.Length;
        int n = nums2.Length;
        int len = m + n;
        var resultIndex = len / 2;

        while (i < m && j < n)
        {
            if (nums1[i] < nums2[j])
                list.Add(nums1[i++]);
            else
                list.Add(nums2[j++]);
        }
        while (i < m) list.Add(nums1[i++]);
        while (j < n) list.Add(nums2[j++]);

        if (len % 2 == 0)
        {
            return (list[resultIndex - 1] + list[resultIndex]) / 2.0;
        }
        else
        {
            return list[resultIndex];
        }
    }
}

2

  • 时间复杂度:O(m+n)
    • i 和 j 一起把长度为 m 和 n 的两个数组遍历了一遍,所以时间复杂度为 O(m+n)
  • 空间复杂度:O(m+n)
    • 使用list的长度为m+n.

C# 解法三:方法二的优化,不真实添加到list

  • 对于方法二,我们在已知 resultIndex 的情况下,也可以不把 nums1 和 nums2 真实添加到 list 中,只需要在i 和 j 不断向右移动的过程中,计算是否到达了 resultIndex 即可。 若到达了 resultIndex,可以直接返回结果,而不必再处理后面的数据。但是相对的,我们需要在 i 或者 j 向右移动时,判断是否到达了resultIndex.
public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int i = 0, j = 0, m = nums1.Length, n = nums2.Length;
        int len = m + n;
        int resultIndex = len / 2;
        int resultIndexPre = resultIndex - 1;
        int result = 0, resultPre = 0;  
        bool isTwoResult = len % 2 == 0;
        while (i < m || j < n)
        {
            var nums1ii = i < m ? nums1[i] : int.MaxValue;
            var nums2jj = j < n ? nums2[j] : int.MaxValue;
            if (nums1ii < nums2jj)
            {
                if (i + j == resultIndexPre) resultPre = nums1[i];
                if (i + j == resultIndex)
                {
                    result = nums1[i];
                    if (isTwoResult) return (resultPre + result) / 2.0;
                    else return result;
                }
                i++;
            }
            else
            {
                if (i + j == resultIndexPre) resultPre = nums2[j];
                if (i + j == resultIndex)
                {
                    result = nums2[j];
                    if (isTwoResult) return (resultPre + result) / 2.0;
                    else return result;
                }
                j++;
            }
        }
        return 0;
    }
}

在这里插入图片描述

  • 时间复杂度:O(m+n)
    • i 和 j 一起把长度为 m 和 n 的两个数组遍历了一半,但是每一步都需要判断当前i+j的值是否等于resultIndex,所以时间复杂度仍可认为 O(m+n)
  • 空间复杂度:O(1)
    • 对比方法二,不再使用list,只使用了几个变量来存值,所以空间复杂度为O(1)

C# 解法四:第k小数

  • 前面的几种方法,时间复杂度都没有达到题目要求的 O(log(m+n)) 。 看到log,很明显需要使用二分法。根据 windliang提供的思路,题目求中位数,实际上是求第 k 小数的一种特殊情况,而求第 k 小数 有一种算法。

方法三中,i 和 j 每次向右移动一位时,相当于去掉了一个不可能是中位数的值,也就是一个一个的排除。由于给定的两个数组是有序的,所以我们完全可以一半一半的排除。假设我们要找第 k 小数,我们每次循环可以安全的排除掉 k/2 个数。

public class Solution {
    public double FindMedianSortedArrays(int[] nums1, int[] nums2)
    {
        int n = nums1.Length;
        int m = nums2.Length;
        int len = n + m;
        int kPre = (len + 1) / 2;
        int k = (len + 2) / 2;
        if (len % 2 == 0)
            return (GetKth(nums1, 0, n - 1, nums2, 0, m - 1, kPre) + GetKth(nums1, 0, n - 1, nums2, 0, m - 1, k)) * 0.5;
        else
            return GetKth(nums1, 0, n - 1, nums2, 0, m - 1, k);
    }

    private 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,这样就能保证如果有数组空了,一定是 len1 
        if (len1 > len2) return GetKth(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 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));
    }
}

1

  • 时间复杂度:O(log(m+n))
    • i每进行依次循环,就减少 k/2个元素,所以时间复杂度为 O(log(k)) , 而 k = (m+n)/2 , 所以最终复杂度是 O(log(m+n))
  • 空间复杂度:O(1)
    • 只使用了几个变量来存值,递归是尾递归不占用堆栈, 所以空间复杂度为O(1)

C# 解法五:从中位数的概念定义入手

public class Solution {
  public double FindMedianSortedArrays(int[] A, int[] B)
    {
        int m = A.Length;
        int n = B.Length;
        //保证第一个数组是较短的
        if (m > n) return FindMedianSortedArrays(B, A);
        //正在寻找的范围为 [ A[iMin],A[iMax] ) , 左闭右开。二分查找取i=(iMin+iMax)/2
        int iMin = 0, iMax = m;
        while (iMin <= iMax)
        {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;
            if (j != 0 && i != m && B[j - 1] > A[i])
            { // i 需要增大
                iMin = i + 1;
            }
            else if (i != 0 && j != n && A[i - 1] > B[j])
            { // i 需要减小
                iMax = i - 1;
            }
            else
            { // 达到要求,并且将边界条件列出来单独考虑
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j - 1]; }
                else if (j == 0) { maxLeft = A[i - 1]; }
                else { maxLeft = Math.Max(A[i - 1], B[j - 1]); }
                if ((m + n) % 2 == 1) { return maxLeft; } // 奇数的话不需要考虑右半部分

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.Min(B[j], A[i]); }

                return (maxLeft + minRight) / 2.0; //如果是偶数的话返回结果
            }
        }
        return 0.0;
    }
}

5

  • 时间复杂度:O(log(min(m,n))
    • 我们对较短的数组进行了二分查找,所以时间复杂度是 O(log(min(m,n))
  • 空间复杂度:O(1)
    • 只使用了几个变量来存值,所以空间复杂度为O(1)
文章来源:https://blog.csdn.net/backlighting2015/article/details/135173051
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。