4. Median of Two Sorted Arrays

2019-11-06 08:19:40

字体：大中小

来源：转载

供稿：网友

There are two sorted arrays nums1 and nums2 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.0Example 2:nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5Subscribe to see which companies asked this question.

重点是编写一个找第k小的数的一个函数，然后根据a、b总数的奇偶性来求答案

double findk(vector<int> &a, int abeg, vector<int> &b, int bbeg,int k){//求a从位置abeg开始，b从bbeg开始，第k小的数 if (a.size() - abeg > b.size() - bbeg) return findk(b, bbeg, a, abeg, k);//保证a有效数目小 if (abeg == a.size()) return b[bbeg+k - 1];//a已经超上限了，或者说空了 if (k == 1) return min(a[abeg], b[bbeg]);//第一个数 int na = min(k / 2, (int)a.size() - abeg), nb = k - na; if (a[abeg + na - 1] < b[bbeg + nb - 1]) return findk(a, abeg + na, b, bbeg, k - na);//舍弃a中小的部分 else if (a[abeg + na - 1] == b[bbeg + nb - 1]) return a[abeg + na - 1]; else return findk(a, abeg, b, bbeg + nb, k - nb);}class Solution {public: double findMedianSortedArrays(vector<int>& a, vector<int>& b) { int k = a.size() + b.size(); if (k % 2) return findk(a, 0, b, 0, k / 2+1); else return (findk(a, 0, b, 0, k / 2) + findk(a, 0, b, 0, k / 2+1))/2; }};

上一篇：网络流24题6. 最长递增子序列问题

下一篇：Joomla（1）搭建Joomla工程总结