力扣刷题之玩转ChatGPT（四、寻找两个正序数组的中位数）

1. 寻找两个正序数组的中位数

给定两个大小分别为 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
-106 <= nums1[i], nums2[i] <= 106

Java 实现：

解题思路：

将原问题转化为寻找两个有序数组的第 k 小的数，其中 k 为两个数组长度之和的一半。

依次比较两个有序数组的前 k/2 个元素，如果 nums1[k/2-1] < nums2[k/2-1]，则 nums1 中的前 k/2 个元素都不可能是第 k 小的数，可以将其排除，然后在剩余的元素中重新查找第 k/2 小的数；如果 nums1[k/2-1] > nums2[k/2-1]，则 nums2 中的前 k/2 个元素都不可能是第 k 小的数，同理，可以将其排除，然后在剩余的元素中重新查找第 k/2 小的数。如果两个数组的前 k/2 个元素相等，则第 k 小的数就是其中任意一个。

递归结束条件为：某一数组为空或者 k=1，此时可以直接返回另一个数组的第 k 个元素。。

Java代码：

class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int n1 = nums1.length;int n2 = nums2.length;int total = n1 + n2;if (total % 2 == 0) { // 如果总长度是偶数return (findKth(nums1, nums2, total / 2) + findKth(nums1, nums2, total / 2 + 1)) / 2.0;} else { // 如果总长度是奇数return findKth(nums1, nums2, total / 2 + 1);}}private int findKth(int[] nums1, int[] nums2, int k) {int n1 = nums1.length;int n2 = nums2.length;if (n1 > n2) { // 保证 nums1 的长度不大于 nums2 的长度return findKth(nums2, nums1, k);}if (n1 == 0) { // 如果 nums1 为空，则第 k 小的数就是 nums2[k-1]return nums2[k - 1];}if (k == 1) { // 如果 k=1，则第 k 小的数是两个数组中最小的那个元素return Math.min(nums1[0], nums2[0]);}int i = Math.min(k / 2, n1); // 分别从 nums1 和 nums2 中查找前 k/2 个元素int j = k - i;if (nums1[i - 1] < nums2[j - 1]) { // 如果 nums1 的第 i 个元素小于 nums2 的第 j 个元素return findKth(Arrays.copyOfRange(nums1, i, n1), nums2, k - i); // 则可以排除 nums1 中的前 i 个元素，重新在剩余数组中查找第 k-i 小的元素} else { // 如果 nums1 的第 i 个元素大于或等于 nums2 的第 j 个元素return findKth(nums1, Arrays.copyOfRange(nums2, j, n2), k - j); // 则可以排除 nums2 中的前 j 个元素，重新在剩余数组中查找第 k-j 小的元素}}
}

Python代码：

class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:n1, n2 = len(nums1), len(nums2)total = n1 + n2if total % 2 == 0:return (self.findKth(nums1, nums2, total // 2) + self.findKth(nums1, nums2, total // 2 + 1)) / 2.0else:return self.findKth(nums1, nums2, total // 2 + 1)def findKth(self, nums1: List[int], nums2: List[int], k: int) -> int:n1, n2 = len(nums1), len(nums2)if n1 > n2:return self.findKth(nums2, nums1, k)if n1 == 0:return nums2[k - 1]if k == 1:return min(nums1[0], nums2[0])i = min(k // 2, n1)j = k - iif nums1[i - 1] < nums2[j - 1]:return self.findKth(nums1[i:], nums2, k - i)else:return self.findKth(nums1, nums2[j:], k - j)

C语言代码：

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){int total = nums1Size + nums2Size;if (total % 2 == 0) {return (findKth(nums1, nums1Size, nums2, nums2Size, total / 2) + findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1)) / 2.0;} else {return findKth(nums1, nums1Size, nums2, nums2Size, total / 2 + 1);}
}int findKth(int* nums1, int nums1Size, int* nums2, int nums2Size, int k){if (nums1Size > nums2Size) {return findKth(nums2, nums2Size, nums1, nums1Size, k);}if (nums1Size == 0) {return nums2[k - 1];}if (k == 1) {return fmin(nums1[0], nums2[0]);}int i = fmin(k / 2, nums1Size);int j = k - i;if (*(nums1 + i - 1) < *(nums2 + j - 1)) {return findKth(nums1 + i, nums1Size - i, nums2, nums2Size, k - i);} else {return findKth(nums1, nums1Size, nums2 + j, nums2Size - j, k - j);}
}

以上文章内容均由ChatGPT3.5版本给出的作答，有问题可以提出来一起探讨！

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！