给定两个大小分别为 m 和 n 的正序(从小到大)数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
题解:采用了遍历的手法,刚好符合log(m + n)的时间复杂度,要注意两个数组总数和为奇数或者偶数的情况
#include "../include/leetcode.h" class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int left = (nums1.size() + nums2.size()) % 2; int medianPositioin = (nums1.size() + nums2.size()) / 2; //两个数组数量加起来是偶数的情况 if (left == 0) { medianPositioin -= 1; } int index = 0; int i1, i2; double currentNum; for (i1 = i2 = 0; i1 < nums1.size() && i2 < nums2.size() && index <= medianPositioin;) { currentNum = nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2]; if (currentNum == nums1[i1]) { ++i1; } else { ++i2; } index += 1; } for (; i1 < nums1.size() && index <= medianPositioin; ++i1) { currentNum = nums1[i1]; index += 1; } for (; i2 < nums2.size() && index <= medianPositioin; ++i2) { currentNum = nums2[i2]; index += 1; } if(left == 1) { return currentNum; } else { double currentNextNum; if (i1 < nums1.size() && i2 < nums2.size()) { currentNextNum = nums1[i1] < nums2[i2] ? nums1[i1] : nums2[i2]; } else if (i1 < nums1.size()) { currentNextNum = nums1[i1]; } else if (i2 < nums2.size()){ currentNextNum = nums2[i2]; } return (currentNextNum + currentNum) / 2; } } }; int main() { Solution s; vector<int> nums1{}; vector<int> nums2{1}; cout << s.findMedianSortedArrays(nums1, nums2) << endl; return 0; }
标签:正序,int,中位数,数组,nums1,nums2,size From: https://www.cnblogs.com/woodx/p/17134528.html