时间轴
时间轴
2025-12-04
init
分治
题目：
O((m+n)/2)解法，合并数组，不过还能优化（当一个数组已经为空时，可以直接计算中位数）
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 | using std::vector;class Solution { public: double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { int m = nums1.size(), n = nums2.size(); int last_num; int mi = 0, ni = 0; int index = 0; int total = m + n; double res = 0; while (mi < m || ni < n) { if (mi < m && ni < n) { if (nums1[mi] < nums2[ni]) { last_num = nums1[mi++]; } else { last_num = nums2[ni++]; } } else if (mi >= m && ni < n) { last_num = nums2[ni++]; } else if (mi < m && ni >= n) { last_num = nums1[mi++]; } if (total % 2 == 0) { if(index == total / 2 - 1){ res += last_num; }else if(index == total / 2){ res += last_num; res = (double) res/2; break; } } else { if (index == total / 2) { res = last_num; break; } } index++; } return res; }}; |
二分法：
根据中位数的定义：
- 当
m+n是奇数时，中位数是两个有序数组中的第(m+n+1)/2个元素 - 当
m+n是偶数时，中位数是两个有序数组中的第(m+n)/2个元素和第(m+n)/2+1个元素的平均值。
因此，这道题可以转化成寻找两个有序数组中的第 k 小的数，其中 k 为(m+n)/2或(m+n)/2+1。
核心思想就是：每次删除 k/2 个元素（每次排除 k/2 个不可能的元素）
设：pivot1 = nums1[k/2-1],pivot2 = nums2[k/2-1], 比较：pivot1 vs pivot2, 初始index1和index2均为0
情况1 :
pivot1 <= pivot2说明：
nums1[0...k/2-1]都不可能是第k小，因为nums1 <= pivot1的最多k/2个,nums2 <= pivot2的最多k/2-1个, 总共<= k-1因此：
nums1前k/2个全部删除更新：
index1 += k/2,k -= k/2
情况2：
pivot2 < pivot1- 同理：
nums2前k/2个删除 - 更新：
index2 += k/2,k -= k/2
- 同理：
此外有三种边界情况，循环开始先处理边界：
- 一个数组已经空了
例如：nums1 = [],nums2 = [1,2,3,4], 第 k 小就是：nums2[k-1]
1234 | if (index1 == m) return nums2[index2 + k - 1];if (index2 == n) return nums1[index1 + k - 1]; |
k == 1
第1小 = 两数组最小值
1 | return min(nums1[index1], nums2[index2]); |
- 正常二分删除
不断减少k直到：k == 1
代码：
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576 | using std::vector;class Solution { public: int getKthElement(const vector<int> &nums1, const vector<int> &nums2, int k) { /* * 主要思路：要找到第 k (k>1) 小的元素，那么就取 * 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(); int n = nums2.size(); int idx1 = 0, idx2 = 0; int new_idx1, new_idx2, pivot1, pivot2; while (true) { // 边界情况 if (idx1 == m) return nums2[idx2 + k - 1]; if (idx2 == n) return nums1[idx1 + k - 1]; if (k == 1) return std::min(nums1[idx1], nums2[idx2]); // 正常情况 new_idx1 = std::min(idx1 + k / 2 - 1, m - 1); new_idx2 = std::min(idx2 + k / 2 - 1, n - 1); pivot1 = nums1[new_idx1]; pivot2 = nums2[new_idx2]; if (pivot1 <= pivot2) { k -= new_idx1 - idx1 + 1; idx1 = new_idx1 + 1; } else { k -= new_idx2 - idx2 + 1; idx2 = new_idx2 + 1; } } } double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) { int total_len = nums1.size() + nums2.size(); int k, val1, val2; if (total_len % 2 == 1) { // 奇数 k = (total_len + 1) / 2; return getKthElement(nums1, nums2, k); } else { // 偶数 k = total_len / 2; val1 = getKthElement(nums1, nums2, k); k = total_len / 2 + 1; val2 = getKthElement(nums1, nums2, k); return (val1 + val2) / 2.0; } }}; |
hot 100 rewrite: 没写出来哈哈哈，这个二分有点难想到