【LeetCode】修炼之路-0004-Median of Two Sorted Arrays【python】

题目

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

思路

一根筋直觉

思路1：直觉，我应该把2个列表合并，通过数组长度n，定位到下标n/2

那我的代码可能需要几个部分呢

1.接收传进来的参数（刷leetcode的话，会发现官方函数定义，已经完成了这个工作，）

我们可以直接用nums1和nums2

2.合并在一起
这里我们定义一个merge函数，然后拿到两个列表的长度，用i和j去边比较，边合并。到循环结束的时候，merged.exted会加一个空的和剩下的那个长的。

def merge(self, nums1: List[int], nums2: List[int]) -> List[int]:merged = []i, j = 0, 0# 比较两个数组的元素并合并while i < len(nums1) and j < len(nums2):if nums1[i] <= nums2[j]:merged.append(nums1[i])i += 1else:merged.append(nums2[j])j += 1# 添加剩余的元素merged.extend(nums1[i:])merged.extend(nums2[j:])

oi, 我们用的是python啊

# 有sorted，直接帮我们排好了
merged = sorted(nums1 + nums2)

3.根据数组是奇数还是偶数，取中间的即可

n = len(merged)# 如果长度为奇数，返回中间元素
if n % 2 == 1:return merged[n // 2]
# 如果长度为偶数，返回中间两个元素的平均值
else:# 假如是1 2 3 4    n//2下标变成2，这个时候对应的是第3个数，所以，偶数是取n//2-1和n//2return (merged[n // 2 - 1] + merged[n // 2]) / 2

最后的莽夫代码：

    
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:# 合并两个有序数组merged = sorted(nums1 + nums2)n = len(merged)# 如果长度为奇数，返回中间元素if n % 2 == 1:return merged[n // 2]# 如果长度为偶数，返回中间两个元素的平均值else:return (merged[n // 2 - 1] + merged[n // 2]) / 2

（怎么回事，我们的暴力算法这么快）

递归思想

思路2.其实我一开始就知道我要找的是第几位，我可以先找第一位，然后找第二位，然后找到第n位

这样我们需要实现一个查找第k个大的值的函数findKthElement()
然后主函数findMedianSortedArrays()需要做的事情就是根据总长度n是奇数还是偶数来决定需要找N//2+1或者找第N//2大的和第N/2+1大的值。

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:total = len(nums1) + len(nums2)if total % 2 == 1:return self.findKthElement(nums1, nums2, total // 2 + 1)else:return (self.findKthElement(nums1, nums2, total // 2) + self.findKthElement(nums1, nums2, total // 2 + 1)) / 2def findKthElement(self, nums1: List[int], nums2: List[int], k: int) -> float:index1, index2 = 0, 0current = 0for _ in range(k):if index1 == len(nums1):current = nums2[index2]index2 += 1elif index2 == len(nums2):current = nums1[index1]index1 += 1elif nums1[index1] < nums2[index2]:current = nums1[index1]index1 += 1else:current = nums2[index2]index2 += 1return current

findKthElement函数开始时，index1 和 index2 都是 0，表示我们从两个数组的开始位置开始。
我们用一个 for 循环来找第 k 个元素。每次循环，我们都会选择一个元素（第 1 个、第 2 个、…、直到第 k 个）。
在每次循环中：
如果 index1 == len(nums1)，这意味着 nums1 已经用完了。我们只能从 nums2 中取元素。
如果 index2 == len(nums2)，这意味着 nums2 已经用完了。我们只能从 nums1 中取元素。
如果两个数组都还有元素(一般状态)，我们比较 nums1[index1] 和 nums2[index2]，选择较小的那个。
每次我们选择一个元素后，我们就把它赋值给 current，并将相应的索引加 1。
当循环结束时，我们已经找到了第 k 个元素，它就是 current。

知识点：当 index 等于数组长度时，这就表示我们已经遍历完了这个数组。
例如，对于长度为 4 的数组：

开始时 index = 0，对应第 1 个元素
然后 index = 1，对应第 2 个元素
然后 index = 2，对应第 3 个元素
然后 index = 3，对应第 4 个元素
最后 index = 4，这时 index 等于数组长度，表示数组已经遍历完毕

提交后，唔，看上去还是有一点可取之处

有序就可以二分

思路3：我的两个列表是有序的，有序就可以二分，通过二分去更快地找第n位
这部分看最佳实践就好了，相关代码应该很多，看看后续补档有空再来更新这部分