LeetCode 4——两个排序数组中的中位数

wawor4827 发布于2019-07-31 11:18 / 1103人阅读

摘要：题目解答方法一由于两个数组都是排好序的，因此首先可以想到的思路就是利用归并排序把两个数组合并成一个有序的长数组，然后直接取出中位数即可。如果满足条件，则直接返回求取中位数。如果减小，则增加，左边序列数组的值会更小，右边序列数组的值会更大。

1. 题目

2. 解答

2.1. 方法一

由于两个数组都是排好序的，因此首先可以想到的思路就是利用归并排序把两个数组合并成一个有序的长数组，然后直接取出中位数即可。

</>复制代码 
class Solution:
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        
        len1 = len(nums1)
        len2 = len(nums2)
        nums = []
        
        i = 0
        j = 0
        
        while (i < len1 and j < len2):
            
            if (nums1[i] <= nums2[j]):
                nums.append(nums1[i])
                i += 1
            
            else:
                nums.append(nums2[j])
                j += 1
        
        if (i < len1):
            while(i < len1):
                nums.append(nums1[i])
                i += 1
            
        if (j < len2):
            while(j < len2):
                nums.append(nums2[j])
                j += 1
        
        odd = (len1 + len2) % 2 # 长度是否为奇数
        mid = (len1 + len2 - 1) // 2
        if (odd):
            return nums[mid]
        else:
            return (nums[mid] + nums[mid+1]) / 2

因为要遍历两个数组，所以时间复杂度为 $O(m+n)$，而题目中要求算法的时间复杂度为 $O(log (m+n))$，因此应该是有更高效的算法，借助于二分查找。

2.2. 方法二

</>复制代码 
所谓中位数，就是将 K 个数据分为长度相等的两组，左边的数据小于等于右边的数据。

如果我们要在任意位置 $i$ 处将长度为 $m$ 的数组 $A$ 分为两部分，则共有 $m+1$ 种分法，$i=[0, m]$。

$$ left\_part quad | quad right\_part$$
$$ A[0], A[1], ..., A[i-1] quad | quad A[i], A[i+1], ..., A[m-1]$$

$i=0$ 说明左半部分没有元素，反之 $i=m$ 说明右半部分没有元素。左半边元素个数为 $i$ ，右半边元素个数为$m-i$。

同理，我们可以在任意位置 $j$ 处将长度为 $n$ 的数组 $B$ 分为两部分，则共有 $n+1$ 种分法，$j=[0, n]$。

$$ B[0], B[1], ..., B[j-1] quad | quad B[j], B[j+1], ..., B[n-1]$$

针对划分完后的数组 $A$ 和 $B$，如果满足：

左边部分的长度等于右边部分的长度（偶数情况），$i+j = m-i + n-j$；或者等于右边部分的长度加 1（奇数情况） ,$i+j = m-i + n-j+1$。

左边的最大元素小于等于右边的最小元素，$A[i-1] <= B[j] quad and quad B[i-1] <= A[j]$。

那我们也就找到了中位数，$median = frac{max(left\_part) + min(right\_part)}{2}$。

所以，我们要做的就是在 $i=[0, m]$ 区间搜索一个 $i$ 值，使得上面的条件得到满足。也即

$$ A[i-1] <= B[j] quad and quad B[i-1] <= A[j] ，其中 quad j = frac{m+n+[1]}{2}-i$$

加不加 1 取决于总的长度是奇数还是偶数，同时，为了保证 $j$ 的范围在 $[0, n]$，我们必须要求 $n <= m$。

接下来，我们就在 $i=[0, m]$ 区间进行二分查找。

如果满足条件，则直接返回求取中位数。

如果 $i > 0 quad and quad A[i-1] > B[j]$，则减小 $i$。如果增加 $i$，则 $j$ 减小，左边序列数组 $A$ 的值会更大，右边序列数组 $B$ 的值会更小。

如果 $i < m quad and quad B[i-1] > A[j]$，则增加 $i$。如果减小 $i$，则 $j$ 增加，左边序列数组 $A$ 的值会更小，右边序列数组 $B$ 的值会更大。

最后，我们求得左半部分的最大值以及右半部分的最小值，然后就可以求出中位数了。

因为，要查找的范围为 $i=[0, m]$，而且每次查找缩小区间为原来的一半，因此时间复杂度为 $O(log(min(m, n))$，空间复杂度为 $O(1)$。

</>复制代码 
class Solution {
public:
    double findMedianSortedArrays(vector& nums1, vector& nums2) {
        
        
        int m = nums1.size();
        int n = nums2.size();
        int len = m + n;
        int odd = len % 2;
        
        int left = 0;
        int i = 0, j = 0;  
        vector::iterator A = nums1.begin();
        vector::iterator B = nums2.begin();
        
        // 确保数组 A 的长度小于等于数组 B 的长度
        if (m > n)
        {
            int temp = m;
            m = n;
            n = temp;
            A = nums2.begin();
            B = nums1.begin();
        }
        
        int right = m;
                
        while(left <= right)
        {
            i = left + (right - left) / 2;
            j = (len + odd) / 2 - i;
                        
            if (i > 0 && A[i-1] > B[j])
            {
                right = i - 1;
            }
            else if(i < m && B[j-1] > A[i])
            {
                left = i + 1;
            }
            else
            {
                break;
            } 
        }
         
        int left_max = 0;
        int right_min = 0;
        
        // 左半部分的最大值
        if (i == 0) left_max = B[j-1];
        else if (j == 0) left_max = A[i-1];
        else  left_max = A[i-1] <= B[j-1] ? B[j-1] : A[i-1];
        // 右半部分的最小值
        if (i == m) right_min = B[j];
        else if (j == n) right_min = A[i];
        else    right_min = A[i] <= B[j] ? A[i] : B[j];
        if (odd)
        {
            return left_max;
        }
        else
        {
            return float(left_max + right_min) / 2;
        }
    }
};

获取更多精彩，请关注「seniusen」!

GPU云服务器云服务器两个数组 asp中的表格排序数组排序数组排序类

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/44957.html

Leetcode-4 Median of Two Sorted Arrays

摘要：解法解法应该是最常见的一种解法，就是将两个数组头尾相加合并起来，然后重新排序，例如输入两个数组，合并之后变为，然后求出中位数。如果两个数组长度和为偶数，那么中位数有两个，否则只有一个题目 There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the tw...

Shihira 2019-08-16 13:50 评论0 收藏0
Leetcode 4 Median of Two Sorted Arrays 两排序数组的中位数

摘要：难度为这个题目描述很清晰给出两个排序好的数组求这两个数组的中位数在解这个题的过程中会碰到以下的问题先合起来重新排序是不可行的时间复杂度太高为先归并排序也是不可行的时间复杂度为用类似桶排的方法时间复杂度为不可行可能会碰到多种全部大于或全部小于 There are two sorted arrays nums1 and nums2 of size m and n respectively...

wudengzan 2019-08-14 17:05 评论0 收藏0
6-9月技术文章汇总

摘要：分布式的管理和当我在谈论架构时我在谈啥状态码详解无状态协议和请求支持哪些方法分层协议栈有哪些数据结构运用场景说说你常用的命令为什么要有包装类面向对象的特征是啥是啥有什么好处系统设计工程在线诊断系统设计与实现索引背后的数据结构及算法原理软技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】当我在谈论RestFul架构时我在谈啥？...

miya 2019-07-30 18:03 评论0 收藏0
JS算法题之leetcode(1~10)

摘要：先去空白，去掉空白之后取第一个字符，判断正负符号，若是英文直接返回，若数字则不取。回文数题目描述判断一个整数是否是回文数。回文数是指正序从左向右和倒序从右向左读都是一样的整数。 JS算法题之leetcode(1~10) 前言一直以来，前端开发的知识储备在数据结构以及算法层面是有所暂缺的，可能归根于我们的前端开发的业务性质，但是我认为任何的编程岗位都离不开数据结构以及算法。因此，我作为...

SoapEye 2019-08-26 10:44 评论0 收藏0
[Leetcode] Median of Two Sorted Arrays 有序数组中位数

摘要：最新解法及思路有两个有序数组和，他们的大小各是和，请找出这两个数组所有数的中位数，总得时间复杂度不超过归并计数法复杂度时间空间思路如果对时间复杂度没有要求，这个方法是实现起来最简单的，我们只需要从下往上依次数个元素即可。 Median of Two Sorted Arrays 最新解法及思路：https://yanjia.li/zh/2018/11/... There are two...

wuaiqiu 2019-08-14 12:17 评论0 收藏0