type
Post
status
Published
date
Mar 23, 2023
slug
summary
给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。算法的时间复杂度应该为 O(log (m+n)) 。
tags
c++
leetcode
category
算法
icon
password
 

题解

给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
 

代码

class Solution { public: int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) { int m = nums1.size(); int n = nums2.size(); int index1 = 0, index2 = 0; while (1) { // 边界情况 // index1==m 说明 nums1 已经遍历完,都不属于要找的第k个数,所以从nums2中找剩余的k个 if (index1 == m) { return nums2[index2 + k - 1]; } // 同上 if (index2 == n) { return nums1[index1 + k - 1]; } // 当k为1 且两个数组都没遍历完,就选择两个数组最左元素最小的值,index指向数组当前最左元素 if (k == 1) { return min(nums1[index1], nums2[index2]); } // 正常情况 // newIndex 用于对比两个序列中下标为 k/2 元素的大小 int newIndex1 = min(index1 + k / 2 - 1, m - 1); int newIndex2 = min(index2 + k / 2 - 1, n - 1); if (nums1[newIndex1] <= nums2[newIndex2]) { // 因为 nums1[newIndex1]小,所以该序列前 k/2个元素比第 k 个元素小,所以可以不在考虑这些元素 // 所以当前 k 值是删除这些元素数量后剩余需要找的k个数。index 后移,指向 k/2 个元素后的第一个元素 k -= newIndex1 - index1 + 1; index1 = newIndex1 + 1; } else { k -= newIndex2 - index2 + 1; index2 = newIndex2 + 1; } } } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int len = nums1.size() + nums2.size(); if (len % 2 == 1) { return getKthElement(nums1, nums2, (len + 1) / 2); } else { return (getKthElement(nums1, nums2, len / 2) + getKthElement(nums1, nums2, len / 2 + 1)) / 2.0; } } };
 
 
Linux中的五种 I/O 模型两数相加