当前位置：首页 > news >正文

网页设计旅游网站源代码免费嘉兴云推广网站

news 2025/11/2 13:55:34

网页设计旅游网站源代码免费,嘉兴云推广网站,phpcms网站备份,怎样做网站xml. - 力扣（LeetCode） 题目给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。算法的时间复杂度应该为 O(log (mn)) 。示例 1： 输入：nums1 …

. - 力扣（LeetCode）

题目

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

算法的时间复杂度应该为 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
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
$-10^6 <= nums1[i], nums2[i] <= 10^6$

解题方案

首先明确中位数的位置

1. 暴力解法（合并数组）

合并成一个新数组，然后sort，取中位数。

边界情况：合并后数组的长度为0，则无中位数
合并数组(nums)长度为偶数(n)，则中位数为第 $\frac{n}{2}$ 位和第 $\frac{n}{2}+1$ 位的平均值，即 $mid=\frac{nums[\frac{n}{2}-1]+nums[\frac{n}{2}]}{2}$
合并数组(nums)长度为奇数(n)，则中位数为第 $\frac{n+1}{2}$ 位，即 $nums[\frac{n-1}{2}]$

接下来，人生苦短，我用Python~

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# 合并数组并排序nums1.extend(nums2)nums1.sort()length = len(nums1)if length < 1:return Noneif length % 2 == 0:return (nums1[length // 2 - 1] + nums1[length // 2]) / 2else:return nums1[length // 2]

分析时空复杂度

记nums1长度为m, nums2长度为n
合并数组时间复杂度是 $O(m+n)$ ，空间复杂度是 $O(m+n)$
数组排序时间复杂度是 $O((n+m)log(n+m))$ ，空间复杂度是 $O((n+m)log(n+m))$

故总的时间复杂度是 $O((n+m)log(n+m))$ ，空间复杂度是 $O((n+m)log(n+m))$

虽然看上去代码非常精炼，但是从时空复杂度上看，算法并不好，毕竟题目中"正序（从小到大）数组"这个条件没有用到。因此考虑有序归并

2. 暴力解法优化版（有序合并数组）

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:m = len(nums1)n = len(nums2)# 合并数组nums = []if m == 0:nums = nums2elif n == 0:nums = nums1else:index_1 = 0index_2 = 0while True:if index_1 >= m and index_2 >= n:breakelif index_2 >= n or (index_1 < m and nums1[index_1] <= nums2[index_2]):nums.append(nums1[index_1])index_1 += 1elif index_1 >=m or (index_2 < n and nums1[index_1] > nums2[index_2]):nums.append(nums2[index_2])index_2 += 1total_length = len(nums)if total_length < 1:return Noneelif total_length % 2 == 0:return (nums[total_length // 2 - 1] + nums[total_length // 2]) / 2else:return nums[total_length // 2]

分析时空复杂度

时间复杂度为合并数组花费的时间， $O(m+n)$
空间复杂度为合并后数组的空间， $O(m+n)$ （如果不存储合并的数组，空间复杂度可以做到O(1)）

题目给出的条件都用上了，时空复杂度也得到了提升，但仍然不符合题目要求的 O(log (m+n))的时间复杂度，需要进一步优化。

有序数组寻找中位数，考虑二分法。

`3. 二分法`

考虑一个长度为n有序数组的中位数，其中位数：

如果n为奇数，则中位数为第 $\frac{n+1}{2}$ 大的数。
如果n为偶数，则中位数为第 $\frac{n}{2}$ 大的数和第 $\frac{n+1}{2}$ 大的数的平均值。

因此，中位数问题可以转换为另一个问题，寻找数组中第k小的数

（对于长度为偶数的情况，需要寻找两次，并取平均值）

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""寻找两个正序整数数组中，第k小的数"""passdef findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""中位数计算入口函数"""total_length = len(num1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(num1, nums2, total_length // 2 + 1)

接着看如何寻找两个正序数组中第k小的数：

如果时间复杂度是O(log (m+n))，考虑用二分法。

先看下面这个例子：

由此，我们可以总结我们两个正序数组中，寻找第k小的数的思路：

1. 如果k=1, 则首先比较两个数组首位元素，取最小的一个。

2. 如果k>1, 则比较两个数组中第 $\frac{k}{2}$ 个元素，较小的一个数组中的第1~ $\frac{k}{2}$ 个元素一定是小于我们目标值的，因此可以排除这一段（如上图中灰色部分），在剩余元素中继续寻找第( $k-\frac{k}{2}$ )小的元素。

3. 如果某个数组完全被排除掉了，则直接在剩余的另一个数组中定位目标元素即可。如下面的例子：

class Solution:def getKthNumber(self,  nums1: List[int], nums2: List[int], k: int) -> int:"""寻找两个正序整数数组中，第k大的数"""# 记录数组长度m = len(nums1)n = len(nums2)# 记录数组可以查找的起始位置索引index_1 = 0index_2 = 0while True:# 极端情况1 - nums1已经被排除为空if index_1 >= m:return nums2[index_2 + k - 1]# 极端情况2 - nums2已经被排除为空if index_2 >= n:return nums1[index_1 + k - 1]# 极端情况3 - 寻找最小的数if k == 1:return min(nums1[index_1], nums2[index_2])# 正常情况, 二分查找new_index_1 = min(k // 2 - 1 + index_1, m - 1)new_index_2 = min(k // 2 - 1 + index_2, n - 1)if nums1[new_index_1] <= nums2[new_index_2]:k -= (new_index_1 - index_1 + 1)index_1 = new_index_1 + 1else:k -= (new_index_2 - index_2 + 1)index_2 = new_index_2 + 1def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:"""寻找中位数 入口函数"""total_length = len(nums1) + len(nums2)if total_length < 1:return Noneelif total_length % 2 == 0:return (self.getKthNumber(nums1, nums2, total_length // 2) + self.getKthNumber(nums1, nums2, total_length // 2 + 1)) / 2else:return self.getKthNumber(nums1, nums2, total_length // 2 + 1)

分析时空复杂度

时间复杂度 $O(log(m+n))$
空间复杂度 $O(1)$

AI会怎么做？

智谱清言给出了一种更高效的解法，划分数组二分法。

思路：

对一个长度为n的数组，从任意位置i将数组划分为两部分，可以有n+1种分发（ $i \in [0, n]$ ），如图所示，4个元素的数组，有4+1=5种划分方法。

中位数的作用是什么呢？将一个集合划分为两个长度相等的子集，其中一个子集中的元素总是大于另一个子集中的元素。
对数组A从i位置进行划分，对数组B在j位置划分，数组A的左半部分和数组B的左半部分合起来叫做left_part, 数组A的有半部分和数组B的右半部分合起来叫做right_part，则中位数是这样的一种划分：
对于两个数组长度之和为偶数的情况： $\left\{\begin{matrix} {len(left\_part) == len(right\_part) }\\{max(left\_part) <= min(right\_part)} \end{matrix}\right.$ ，中位数为 $mid=\frac{max(left\_part)+min(right\_part)}{2}$ ,此时划分位置满足 $i + j = m-i+n-j\quad i\in[0,m],j\in[0,n]$
对于两个数组长度之和为奇数的情况： $\left\{\begin{matrix} {len(left\_part) == len(right\_part) + 1}\\{max(left\_part) <= min(right\_part)} \end{matrix}\right.$ ，中位数为 $mid = max(left\_part)$ ，此时划分位置满足 $i+j=m-i + n-j +1\quad i\in[0,m],j\in[0,n]$
合并上述两种，可以知道中位数情况下的划分： $i+j =int(\frac{m+n+1}{2}) \qquad i\in[0,m],j\in[0,n]$
如果我们保证 $m <=n$ (避免j计算出负数)，可以导出： $j=int(\frac{m+n+1}{2}) - i \qquad j\in[0,n]$
通过上述推导，中位数问题可以转换为：寻找 $i\in[0,m]$ ，使得： $B[j-1] \leqslant A[i]$ 且 $A[i-1]\leqslant B[j]$ ，其中 $j=int(\frac{m+n+1}{2}) - i$ ，
进一步简化为：在 $[0,m]$ 中寻找最大的 $i$ ，使得 $A[i-1]\leqslant B[j]$ ,其中 $j=int(\frac{m+n+1}{2}) - i$ 。接下来就可以在 $[0,m]$ 上对 $i$ 进行二分查找了。

如此复杂的推导过程，又是担心被AI取代的一天。。。

def findMedianSortedArrays(nums1, nums2):# 确保 nums1 是较短的数组if len(nums1) > len(nums2):nums1, nums2 = nums2, nums1m, n = len(nums1), len(nums2)imin, imax, half_len = 0, m, (m + n + 1) // 2while imin <= imax:i = (imin + imax) // 2j = half_len - iif i < m and nums1[i] < nums2[j - 1]:# i 需要增大imin = i + 1elif i > 0 and nums1[i - 1] > nums2[j]:# i 需要减小imax = i - 1else:# 找到合适的 i 和 jmax_of_left = 0if i == 0: max_of_left = nums2[j - 1]elif j == 0: max_of_left = nums1[i - 1]else: max_of_left = max(nums1[i - 1], nums2[j - 1])if (m + n) % 2 == 1:return max_of_leftmin_of_right = 0if i == m: min_of_right = nums2[j]elif j == n: min_of_right = nums1[i]else: min_of_right = min(nums1[i], nums2[j])return (max_of_left + min_of_right) / 2.0# 示例
print(findMedianSortedArrays([1, 3], [2]))  # 输出: 2.0
print(findMedianSortedArrays([1, 2], [3, 4]))  # 输出: 2.5

查看全文

http://www.yayakq.cn/news/711305/