html5 单页网站,建设企业网站网站崩溃,app store免费下载,成免费crm不用下载题目描述 给定两个大小分别为 m 和 n 的正序#xff08;从小到大#xff09;数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 1.二分查找
1.1思路 时间复杂度#xff1a;O(log(mn)) 空间复杂度#xff1a;O(1) 给定…题目描述 给定两个大小分别为 m 和 n 的正序从小到大数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (mn)) 。 1.二分查找
1.1思路 时间复杂度O(log(mn)) 空间复杂度O(1) 给定两个有序数组要求找到两个有序数组的中位数最直观的思路有以下两种 1使用归并的方式合并两个有序数组得到一个大的有序数组。大的有序数组的中间位置的元素即为中位数。 2不需要合并两个有序数组只要找到中位数的位置即可。由于两个数组的长度已知因此中位数对应的两个数组的下标之和也是已知的。维护两个指针初始时分别指向两个数组的下标 0 的位置每次将指向较小值的指针后移一位如果一个指针已经到达数组末尾则只需要移动另一个数组的指针直到到达中位数的位置。 假设两个有序数组的长度分别为 m 和 n上述两种思路的复杂度如何 第一种思路的时间复杂度是 O(mn)空间复杂度是 O(mn)。第二种思路虽然可以将空间复杂度降到 O(1)但是时间复杂度仍是 O(mn)。 如何把时间复杂度降低到 O(log(mn)) 呢如果对时间复杂度的要求有 log通常都需要用到二分查找这道题也可以通过二分查找实现。 根据中位数的定义当 mn 是奇数时中位数是两个有序数组中的第 (mn)/2 个元素当 mn 是偶数时中位数是两个有序数组中的第 (mn)/2 个元素和第 (mn)/21 个元素的平均值。因此这道题可以转化成寻找两个有序数组中的第 k 小的数其中 k 为 (mn)/2 或 (mn)/21。 假设两个有序数组分别是 A 和 B。要找到第 k 个元素我们可以比较 A[k/2−1] 和 B[k/2−1]其中 / 表示整数除法。由于 A[k/2−1] 和 B[k/2−1] 的前面分别有 A[0..k/2−2] 和 B[0..k/2−2]即 k/2−1 个元素对于 A[k/2−1] 和 B[k/2−1] 中的较小值最多只会有 (k/2−1)(k/2−1)≤k−2 个元素比它小那么它就不能是第 k 小的数了。 因此我们可以归纳出三种情况 1如果 A[k/2−1]B[k/2−1]则比 A[k/2−1] 小的数最多只有 A 的前 k/2−1 个数和 B 的前 k/2−1 个数即比 A[k/2−1] 小的数最多只有 k−2 个因此 A[k/2−1] 不可能是第 k 个数A[0] 到 A[k/2−1] 也都不可能是第 k 个数可以全部排除。 2如果 A[k/2−1]B[k/2−1]则可以排除 B[0] 到 B[k/2−1]。 3如果 A[k/2−1]B[k/2−1]则可以归入第一种情况处理。 可以看到比较 A[k/2−1] 和 B[k/2−1] 之后可以排除 k/2 个不可能是第 k 小的数查找范围缩小了一半。同时我们将在排除后的新数组上继续进行二分查找并且根据我们排除数的个数减少 k 的值这是因为我们排除的数都不大于第 k 小的数。 有以下三种情况需要特殊处理 1如果 A[k/2−1] 或者 B[k/2−1] 越界那么我们可以选取对应数组中的最后一个元素。在这种情况下我们必须根据排除数的个数减少 k 的值而不能直接将 k 减去 k/2。 2如果一个数组为空说明该数组中的所有元素都被排除我们可以直接返回另一个数组中第 k 小的元素。 3如果 k1我们只要返回两个数组首元素的最小值即可。 1.一个例子 用一个例子说明上述算法。假设两个有序数组如下 A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9两个有序数组的长度分别是 4 和 9长度之和是 13中位数是两个有序数组中的第 7 个元素因此需要找到第 k7 个元素。 比较两个有序数组中下标为 k/2−12 的数即 A[2] 和 B[2]如下面所示 A: 1 3 4 9↑
B: 1 2 3 4 5 6 7 8 9↑由于 A[2]B[2]因此排除 B[0] 到 B[2]即数组 B 的下标偏移 offset 变为 3同时更新 k 的值kk−k/24。 下一步寻找比较两个有序数组中下标为 k/2−11 的数即 A[1] 和 B[4]如下面所示其中方括号部分表示已经被排除的数。 A: 1 3 4 9↑
B: [1 2 3] 4 5 6 7 8 9↑由于 A[1]B[4]因此排除 A[0] 到 A[1]即数组 A 的下标偏移变为 2同时更新 k 的值kk−k/22。 下一步寻找比较两个有序数组中下标为 k/2−10 的数即比较 A[2] 和 B[3]如下面所示其中方括号部分表示已经被排除的数。 A: [1 3] 4 9↑
B: [1 2 3] 4 5 6 7 8 9↑由于 A[2]B[3]根据之前的规则排除 A 中的元素因此排除 A[2]即数组 A 的下标偏移变为 3同时更新 k 的值 kk−k/21。 由于 k 的值变成 1因此比较两个有序数组中的未排除下标范围内的第一个数其中较小的数即为第 k 个数由于 A[3]B[3]因此第 k 个数是 B[3]4。 A: [1 3 4] 9↑
B: [1 2 3] 4 5 6 7 8 9↑1.2代码
1.C
class Solution {
public:// 此函数作用寻找两有序数组 nums1 和 nums2 中第 k 小的数并返回该数int getKthElement(const vectorint nums1, const vectorint nums2, int k) {/* 主要思路要找到第 k (k1) 小的元素那么就取 pivot1 nums1[k/2-1] 和 pivot2 nums2[k/2-1] 进行比较* 这里的 / 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个* 取 pivot min(pivot1, pivot2)两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) (k/2-1) k-2 个* 这样 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot pivot1那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums1 数组* 如果 pivot pivot2那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums2 数组* 由于我们 删除 了一些元素这些元素都比第 k 小的元素要小因此需要修改 k 的值减去删除的数的个数*/int m nums1.size(); // 数组 nums1 的大小int n nums2.size(); // 数组 nums2 的大小int index1 0, index2 0; // 数组 nums1 和 nums2 的偏移while (true) {// 边界情况if (index1 m) { // 数组 nums1 为空return nums2[index2 k - 1]; // 返回数组 nums2 中第 k 小的数}if (index2 n) { // 数组 nums2 为空return nums1[index1 k - 1]; // 返回数组 nums1 中第 k 小的数}if (k 1) { // 若 k 1则返回两个有序数组中的未排除下标范围内的第一个数return min(nums1[index1], nums2[index2]);}// 正常情况int newIndex1 min(index1 k / 2 - 1, m - 1); // 数组 nums1 加上偏移后的新下标int newIndex2 min(index2 k / 2 - 1, n - 1); // 数组 nums2 加上偏移后的新下标int pivot1 nums1[newIndex1]; // 数组 nums1 中参与比较的值int pivot2 nums2[newIndex2]; // 数组 nums2 中参与比较的值if (pivot1 pivot2) { // 若 A[k/2-1] B[k/2-1]k - newIndex1 - index1 1; // 更新 k k - k / 2index1 newIndex1 1; // 更新数组 nums1 的偏移值}else { // 若 B[k/2-1] A[k/2-1]k - newIndex2 - index2 1; // 更新 k k - k / 2index2 newIndex2 1; // 更新数组 nums2 的偏移值}}}double findMedianSortedArrays(vectorint nums1, vectorint nums2) {int totalLength nums1.size() nums2.size(); // 两数组总长if (totalLength % 2 1) { // 若总长为奇数// 第 k 小的数即为中位数return getKthElement(nums1, nums2, (totalLength 1) / 2);}else { // 若总长为偶数// 中位数 (第 k 小的数 第 [k 1] 的数) / 2return (getKthElement(nums1, nums2, totalLength / 2) getKthElement(nums1, nums2, totalLength / 2 1)) / 2.0;}}
};2.Python3
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:# 此函数作用寻找两有序数组 nums1 和 nums2 中第 k 小的数并返回该数def getKthElement(k):- 主要思路要找到第 k (k1) 小的元素那么就取 pivot1 nums1[k/2-1] 和 pivot2 nums2[k/2-1] 进行比较- 这里的 / 表示整除- nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个- nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个- 取 pivot min(pivot1, pivot2)两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) (k/2-1) k-2 个- 这样 pivot 本身最大也只能是第 k-1 小的元素- 如果 pivot pivot1那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums1 数组- 如果 pivot pivot2那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums2 数组- 由于我们 删除 了一些元素这些元素都比第 k 小的元素要小因此需要修改 k 的值减去删除的数的个数index1, index2 0, 0 # 数组 nums1 和 nums2 的偏移while True:# 特殊情况if index1 m: # 数组 nums1 为空return nums2[index2 k - 1] # 返回数组 nums2 中第 k 小的数if index2 n: # 数组 nums2 为空return nums1[index1 k - 1] # 返回数组 nums1 中第 k 小的数if k 1: # 若 k 1则返回两个有序数组中的未排除下标范围内的第一个数return min(nums1[index1], nums2[index2])# 正常情况newIndex1 min(index1 k // 2 - 1, m - 1) # 数组 nums1 加上偏移后的新下标newIndex2 min(index2 k // 2 - 1, n - 1) # 数组 nums2 加上偏移后的新下标pivot1, pivot2 nums1[newIndex1], nums2[newIndex2] # 数组 nums1nums2 中参与比较的值if pivot1 pivot2: # 若 A[k/2-1] B[k/2-1]k - newIndex1 - index1 1 # 更新 k k - k / 2index1 newIndex1 1 # 更新数组 nums1 的偏移值else: # 若 B[k/2-1] A[k/2-1]k - newIndex2 - index2 1 # 更新 k k - k / 2index2 newIndex2 1 # 更新数组 nums1 的偏移值m, n len(nums1), len(nums2) # 数组 nums1nums2 的长度totalLength m n # 数组 nums1nums2 的总长度if totalLength % 2 1: # 若总长度为奇数return getKthElement((totalLength 1) // 2) # 第 k 小的数即为中位数else: # 若总长为偶数# 中位数 (第 k 小的数 第 [k 1] 的数) / 2return (getKthElement(totalLength // 2) getKthElement(totalLength // 2 1)) / 23.Java
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {int length1 nums1.length, length2 nums2.length;int totalLength length1 length2;if (totalLength % 2 1) {int midIndex totalLength / 2;double median getKthElement(nums1, nums2, midIndex 1);return median;} else {int midIndex1 totalLength / 2 - 1, midIndex2 totalLength / 2;double median (getKthElement(nums1, nums2, midIndex1 1) getKthElement(nums1, nums2, midIndex2 1)) / 2.0;return median;}}public int getKthElement(int[] nums1, int[] nums2, int k) {/* 主要思路要找到第 k (k1) 小的元素那么就取 pivot1 nums1[k/2-1] 和 pivot2 nums2[k/2-1] 进行比较* 这里的 / 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共计 k/2-1 个* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共计 k/2-1 个* 取 pivot min(pivot1, pivot2)两个数组中小于等于 pivot 的元素共计不会超过 (k/2-1) (k/2-1) k-2 个* 这样 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot pivot1那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums1 数组* 如果 pivot pivot2那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把这些元素全部 删除剩下的作为新的 nums2 数组* 由于我们 删除 了一些元素这些元素都比第 k 小的元素要小因此需要修改 k 的值减去删除的数的个数*/int length1 nums1.length, length2 nums2.length;int index1 0, index2 0;int kthElement 0;while (true) {// 边界情况if (index1 length1) {return nums2[index2 k - 1];}if (index2 length2) {return nums1[index1 k - 1];}if (k 1) {return Math.min(nums1[index1], nums2[index2]);}// 正常情况int half k / 2;int newIndex1 Math.min(index1 half, length1) - 1;int newIndex2 Math.min(index2 half, length2) - 1;int pivot1 nums1[newIndex1], pivot2 nums2[newIndex2];if (pivot1 pivot2) {k - (newIndex1 - index1 1);index1 newIndex1 1;} else {k - (newIndex2 - index2 1);index2 newIndex2 1;}}}
}4.Golang
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {totalLength : len(nums1) len(nums2)if totalLength%2 1 {midIndex : totalLength/2return float64(getKthElement(nums1, nums2, midIndex 1))} else {midIndex1, midIndex2 : totalLength/2 - 1, totalLength/2return float64(getKthElement(nums1, nums2, midIndex1 1) getKthElement(nums1, nums2, midIndex2 1)) / 2.0}return 0
}func getKthElement(nums1, nums2 []int, k int) int {index1, index2 : 0, 0for {if index1 len(nums1) {return nums2[index2 k - 1]}if index2 len(nums2) {return nums1[index1 k - 1]}if k 1 {return min(nums1[index1], nums2[index2])}half : k/2newIndex1 : min(index1 half, len(nums1)) - 1newIndex2 : min(index2 half, len(nums2)) - 1pivot1, pivot2 : nums1[newIndex1], nums2[newIndex2]if pivot1 pivot2 {k - (newIndex1 - index1 1)index1 newIndex1 1} else {k - (newIndex2 - index2 1)index2 newIndex2 1}}return 0
}func min(x, y int) int {if x y {return x}return y
}2.划分数组
2.1思路 时间复杂度O(log(min(m,n))) 空间复杂度O(1) 二分查找的时间复杂度已经很优秀了但本题存在时间复杂度更低的一种方法。这里给出推导过程勇于挑战自己的读者可以进行尝试。 为了使用划分的方法解决这个问题需要理解「中位数的作用是什么」。在统计中中位数被用来 将一个集合划分为两个长度相等的子集其中一个子集中的元素总是大于另一个子集中的元素。 如果理解了中位数的划分作用就很接近答案了。 首先在任意位置 i 将 A 划分成两个部分 left_A | right_AA[0], A[1], ..., A[i-1] | A[i], A[i1], ..., A[m-1]由于 A 中有 m 个元素 所以有 m1 种划分的方法 i∈[0,m]。 其中len(left_A)i,len(right_A)m−i. 注意当 i0 时left_A 为空集 而当 im 时, right_A 为空集。 采用同样的方式在任意位置 j 将 B 划分成两个部分 left_B | right_BB[0], B[1], ..., B[j-1] | B[j], B[j1], ..., B[n-1]将 left_A 和 left_B 放入一个集合并将 right_A 和 right_B 放入另一个集合。 再把这两个新的集合分别命名为 left_part 和 right_part left_part | right_partA[0], A[1], ..., A[i-1] | A[i], A[i1], ..., A[m-1]B[0], B[1], ..., B[j-1] | B[j], B[j1], ..., B[n-1]当 A 和 B 的总长度是偶数时如果可以确认 len(left_part)len(right_part) max(left_part)≤min(right_part) 那么{A,B} 中的所有元素已经被划分为相同长度的两个部分且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值和后一部分的最小值的平均值 median [max(left_part) min(right_part)] / 2 当 A 和 B 的总长度是奇数时如果可以确认 len(left_part)len(right_part)1 max(left_part)≤min(right_part) 那么{A,B} 中的所有元素已经被划分为两个部分前一部分比后一部分多一个元素且前一部分中的元素总是小于或等于后一部分中的元素。中位数就是前一部分的最大值 medianmax(left_part) 第一个条件对于总长度是偶数和奇数的情况有所不同但是可以将两种情况合并。第二个条件对于总长度是偶数和奇数的情况是一样的。 要确保这两个条件只需要保证 1ijm−in−j当 mn 为偶数或 ijm−in−j1当 mn 为奇数。 等号左侧为前一部分的元素个数等号右侧为后一部分的元素个数。 将 i 和 j 全部移到等号左侧我们就可以得到 i j (m n 1) / 2。 这里的分数结果只保留整数部分。 20≤i≤m0≤j≤n。如果我们规定 A 的长度小于等于 B 的长度即m≤n。 这样对于任意的 i∈[0,m]都有 j (m n 1) / 2 - i ∈ [0,n]那么我们在 [0,m] 的范围内枚举 i 并得到 j就不需要额外的性质了。 如果 A 的长度较大那么我们只要交换 A 和 B 即可。 如果 mn 那么得出的 j 有可能是负数。 3B[j−1]≤A[i] 以及 A[i−1]≤B[j]即前一部分的最大值小于等于后一部分的最小值。 为了简化分析假设 A[i−1],B[j−1],A[i],B[j] 总是存在。 对于 i0、im、j0、jn 这样的临界条件我们只需要规定 A[−1]B[−1]−∞A[m]B[n]∞ 即可。 这也是比较直观的 当一个数组不出现在前一部分时对应的值为负无穷就不会对前一部分的 最大值 产生影响 当一个数组不出现在后一部分时对应的值为正无穷就不会对后一部分的 最小值 产生影响。 所以我们需要做的是 在 [0,m] 中找到 i使得 B[j−1]≤A[i] 且 A[i−1]≤B[j]其中 j (m n 1) / 2 - i 我们证明它等价于 在 [0,m] 中找到最大的 i使得A[i−1]≤B[j]其中 j (m n 1) / 2 - i 这是因为 当 i 从 0∼m 递增时A[i−1] 递增B[j] 递减所以一定存在一个最大的 i 满足 A[i−1]≤B[j] 如果 i 是最大的那么说明 i1 不满足。将 i1 带入可以得到A[i]B[j−1]也就是 B[j−1]A[i]就和我们进行等价变换前 i 的性质一致了甚至还要更强。 因此我们可以对 i 在 [0,m] 的区间上进行 二分搜索找到最大的满足 A[i−1]≤B[j] 的 i 值就得到了划分的方法。此时划分前一部分元素中的最大值以及划分后一部分元素中的最小值才可能作为就是这两个数组的中位数。 2.2代码
1.C
class Solution {
public:double findMedianSortedArrays(vectorint nums1, vectorint nums2) {if (nums1.size() nums2.size()) { // 如果数组 nums1 的长度更长return findMedianSortedArrays(nums2, nums1);}int m nums1.size(); // nums1 的大小int n nums2.size(); // nums2 的大小int left 0, right m; // nums1 的左右边界// median1前一部分的最大值// median2后一部分的最小值int median1 0, median2 0;while (left right) {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]int i (left right) / 2; // 二分搜索满足条件的 i此为初值int j (m n 1) / 2 - i; // 基于 i j (m n 1) / 2// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]int nums_im1 (i 0 ? INT_MIN : nums1[i - 1]); // i 0 的情况i - 1 为负无穷int nums_i (i m ? INT_MAX : nums1[i]); // i m 的情况i 正无穷int nums_jm1 (j 0 ? INT_MIN : nums2[j - 1]); // j 0 的情况j - 1 为负无穷int nums_j (j n ? INT_MAX : nums2[j]); // j n 的情况j 正无穷if (nums_im1 nums_j) { // nums1[i - 1] nums2[j] 的情况median1 max(nums_im1, nums_jm1); // 前一部分的最大值max(nums1[i - 1]nums2[j - 1])median2 min(nums_i, nums_j); // 后一部分的最小值min(nums1[i]nums2[j])left i 1; // 更新左边界} else { // nums1[i - 1] nums2[j] 的情况right i - 1; // 更新右边界}}// 根据两个数组的总长度的奇偶情况决定最后返回的中位数return (m n) % 2 0 ? (median1 median2) / 2.0 : median1;}
};2.Python3
class Solution:def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) - float:if len(nums1) len(nums2): # 如果数组 nums1 的长度更长return self.findMedianSortedArrays(nums2, nums1)infinty 2**40 # 定义无穷值m, n len(nums1), len(nums2) # 数组 nums1 和数组 nums2 的长度left, right 0, m # 数组 nums1 的左右边界# median1前一部分的最大值# median2后一部分的最小值median1, median2 0, 0while left right: # 二分查找目标 i# 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]# // 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]i (left right) // 2j (m n 1) // 2 - i # 基于 i j (m n 1) / 2# nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]nums_im1 (-infinty if i 0 else nums1[i - 1]) # 根据 i 的值确定 nums[i - 1] 的值若 i 0则为负无穷nums_i (infinty if i m else nums1[i]) # 根据 i 的值确定 nums[i] 的值若 i m则为正无穷nums_jm1 (-infinty if j 0 else nums2[j - 1]) # 根据 j 的值确定 nums[j - 1] 的值若 j 0则为负无穷nums_j (infinty if j n else nums2[j]) # 根据 j 的值确定 nums[j] 的值若 j n则为正无穷if nums_im1 nums_j: # nums1[i - 1] nums2[j] 的情况# 前一部分的最大值max(nums1[i - 1]nums2[j - 1])后一部分的最小值min(nums1[i]nums2[j])median1, median2 max(nums_im1, nums_jm1), min(nums_i, nums_j)left i 1 # 更新左边界else:right i - 1 # 更新右边界# 根据两个数组的总长度的奇偶情况决定最后返回的中位数return (median1 median2) / 2 if (m n) % 2 0 else median13.Java
class Solution {public double findMedianSortedArrays(int[] nums1, int[] nums2) {if (nums1.length nums2.length) {return findMedianSortedArrays(nums2, nums1);}int m nums1.length;int n nums2.length;int left 0, right m;// median1前一部分的最大值// median2后一部分的最小值int median1 0, median2 0;while (left right) {// 前一部分包含 nums1[0 .. i-1] 和 nums2[0 .. j-1]// 后一部分包含 nums1[i .. m-1] 和 nums2[j .. n-1]int i (left right) / 2;int j (m n 1) / 2 - i;// nums_im1, nums_i, nums_jm1, nums_j 分别表示 nums1[i-1], nums1[i], nums2[j-1], nums2[j]int nums_im1 (i 0 ? Integer.MIN_VALUE : nums1[i - 1]);int nums_i (i m ? Integer.MAX_VALUE : nums1[i]);int nums_jm1 (j 0 ? Integer.MIN_VALUE : nums2[j - 1]);int nums_j (j n ? Integer.MAX_VALUE : nums2[j]);if (nums_im1 nums_j) {median1 Math.max(nums_im1, nums_jm1);median2 Math.min(nums_i, nums_j);left i 1;} else {right i - 1;}}return (m n) % 2 0 ? (median1 median2) / 2.0 : median1;}
}4.Golang
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {if len(nums1) len(nums2) {return findMedianSortedArrays(nums2, nums1)}m, n : len(nums1), len(nums2)left, right : 0, mmedian1, median2 : 0, 0for left right {i : (left right) / 2j : (m n 1) / 2 - inums_im1 : math.MinInt32if i ! 0 {nums_im1 nums1[i-1]}nums_i : math.MaxInt32if i ! m {nums_i nums1[i]}nums_jm1 : math.MinInt32if j ! 0 {nums_jm1 nums2[j-1]}nums_j : math.MaxInt32if j ! n {nums_j nums2[j]}if nums_im1 nums_j {median1 max(nums_im1, nums_jm1)median2 min(nums_i, nums_j)left i 1} else {right i - 1}}if (m n) % 2 0 {return float64(median1 median2) / 2.0}return float64(median1)
}func max(x, y int) int {if x y {return x}return y
}func min(x, y int) int {if x y {return x}return y
}
