引言
题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/description/
题目大意
给出两个升序的有序序列,找到两个序列合并后序列的中位数
Hint: You may assume nums1 and nums2 cannot be both empty.
官方希望复杂度为 O(log(m+n))
题解
对于一个长度为n的已排序数列 nums,
若n为奇数,中位数为 nums[n/2]
若n为偶数,则中位数 (nums[n/2-1] + nums[n/2]) / 2
方法一
一句话题解:走一次归并排序逻辑(先确定中位数下标过程中注意计算即可)
复杂度 O(m+n),(明显和官方要求复杂度不是一个级别,目测后台数据比较水所以过了)
方法二
转换为寻找第k大的数据,类似于快排递归调整数据使得左边所有数据小于当前数据,右边大于等于当前数据这一步骤
详解
假设 nums1和 nums2数组中元素个数都是大于 k/2 的,且从 0 开始编号,比较 a = nums1[k/2-1] 和 b = nums2[k/2-1]
- 如果 a < b 那么 nums1[0] 到 nums1[k/2-1] 这 k/2 个数在合并后的有序数组中,一定在第 k 小的数左边———— nums1数组中比 a 小的数一共是 k/2-1 个。 nums2数组中比 a 小的数最多有 k/2-1 个。因而合并后比 a 小的数最多有k/2-1+k/2-1 < k-2,即 a 最多是第 k-1 小的数。因此nums1数组前 k/2 个数可以剔除了
- 如果 a > b 同理,剔除掉 nums2数组前 k/2 个数
- 如果 a = b,a 即为所求
实际中若 nums1和 nums2数组中元素个数不足 k/2 个的话,只需要前两者分割数据个数等于k即可
复杂度:每次剔除掉 k 一半个元素,即时间复杂度是 O(logk),对于此题, k=(m+n)/2 即复杂度 O(log(m+n))
AC代码
c++版本一(归并排序法,也是博主AC方法,为了不使用额外空间代码写得很挫,不够优雅)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 |
class Solution { public: double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { int total = nums1.size() + nums2.size(); if (0 == total) { return 0; } if (2 == total) { if (0 == nums1.size()) { return (nums2[0] + nums2[1]) * 1.0 / 2; } if (0 == nums2.size()) { return (nums1[0] + nums1[1]) * 1.0 / 2; } return (nums1[0] + nums2[0]) * 1.0 / 2; } double medianNumSum = 0; int medianNum1Index = ((total + 1) >> 1) - 1; int medianNum2Index = total >> 1; int i = 0; int j = 0; for (; i < nums1.size() && j < nums2.size();) { if (nums1[i] < nums2[j]) { ++i; } else { ++j; } if (i + j == medianNum1Index && i < nums1.size() && j < nums2.size()) { medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]); } if (i + j == medianNum2Index && i < nums1.size() && j < nums2.size()) { medianNumSum += (nums1[i] < nums2[j] ? nums1[i] : nums2[j]); } } if (i + j <= medianNum2Index && i < nums1.size()) { for (; i < nums1.size(); ++i) { if (i + j == medianNum1Index) { medianNumSum += nums1[i]; } if (i + j == medianNum2Index) { medianNumSum += nums1[i]; } } } if (i + j <= medianNum2Index && j < nums2.size()) { for (; j < nums2.size(); ++j) { if (i + j == medianNum1Index) { medianNumSum += nums2[j]; } if (i + j == medianNum2Index) { medianNumSum += nums2[j]; } } } return medianNumSum / 2; } }; |
c++版本二
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 |
class Solution { public: double findKthValue(vector<int> &nums1, vector<int> &nums2, int start1, int len1, int start2, int len2, int k) { if (len1 > len2) { return findKthValue(nums2, nums1, start2, len2, start1, len1, k); } if (0 == len1) { return nums2[start2 + k - 1]; } if (1 == k) { return nums1[start1] < nums2[start2] ? nums1[start1] : nums2[start2]; } int p = k / 2 < len1 ? k / 2 : len1; int q = k - p; if (nums1[start1 + p - 1] > nums2[start2 + q - 1]) { return findKthValue(nums1, nums2, start1, len1, start2 + q, len2 - q, k - q); } else if (nums1[start1 + p - 1] < nums2[start2 + q - 1]) { return findKthValue(nums1, nums2, start1 + p, len1 - p, start2, len2, k - p); } else { return nums1[start1 + p - 1]; } } double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { int total = nums1.size() + nums2.size(); if (total & 1) { return findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1); } else { return (findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), total >> 1) + findKthValue(nums1, nums2, 0, nums1.size(), 0, nums2.size(), (total >> 1) + 1)) / 2; } } }; |
go版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
func findKthValue(nums1, nums2 []int, start1, len1, start2, len2, k int) float64 { if len1 > len2 { return findKthValue(nums2, nums1, start2, len2, start1, len1, k) } if 0 == len1 { return float64(nums2[start2+k-1]) } if 1 == k { return math.Min(float64(nums1[start1]), float64(nums2[start2])) } var p, q int if k/2 < len1 { p = k / 2 } else { p = len1 } q = k - p if nums1[start1+p-1] > nums2[start2+q-1] { return findKthValue(nums1, nums2, start1, len1, start2+q, len2-q, k-q) } else if nums1[start1+p-1] < nums2[start2+q-1] { return findKthValue(nums1, nums2, start1+p, len1-p, start2, len2, k-p) } else { return float64(nums1[start1+p-1]) } } func findMedianSortedArrays(nums1 []int, nums2 []int) float64 { lens := len(nums1) + len(nums2) if 1 == lens&1 { return findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1) } else { return (findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2) + findKthValue(nums1, nums2, 0, len(nums1), 0, len(nums2), lens/2+1)) / 2 } } |