本文共 1443 字,大约阅读时间需要 4 分钟。
There are two sorted arrays nums1 andnums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]nums2 = [2]The median is 2.0
Example 2:
nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5
根据题目,两个数组是排好序的。要求这两个数组合起来的数组的中位数。
由于这两个数组是排好序的,可以直接归并为一个排好序的数组,再来求该数组的中位数。但是,该新数组后半部分是不需要用到的,因此,可以在归并为一个数组的过程中判断是否已经排好一半了。
要注意数组的元素个数是奇数还是偶数。还要注意当一个数组全部历遍之后,还没有达到总数一半的边界情况。
class Solution {public: double findMedianSortedArrays(vector & nums1, vector & nums2) { int i = 0, j = 0; int a = 0, b = 0; int totalSize = nums1.size() + nums2.size(); int median = totalSize / 2; for (i = 0, j = 0; i <= nums1.size() || j <= nums2.size();) { if (i == nums1.size()) { a = b; b = nums2[j]; j++; } else if (j == nums2.size()) { a = b; b = nums1[i]; i++; } else if (nums1[i] <= nums2[j]) { a = b; b = nums1[i]; i++; } else { a = b; b = nums2[j]; j++; } if (i+j == median + 1) { if (totalSize % 2 == 0) { return (a+b)/2.0; } else { return b; } } } }};
转载地址:http://vibmb.baihongyu.com/