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工程總結