题目地址 ： https://leetcode.com/PRoblems/median-of-two-sorted-arrays/?tab=Description 题目描述 ： 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)).
我的代码 ：
/* 当m+n是奇数时，中位数即是低（m+n+1）/2大的数；当m+n是偶数时，中位数是第(m+n)/2和(m+n)/2+1大的数的平均。由此只需求第k大的数的函数。 不妨设两个数组的长度有n>=m，显然当m=0时直接可得，当k=1时为两个数组第一个数的最小者，而当m>0且k>1时，则令i=min（m，k/2），显然0<i<k;令j=k-i；比较数组n的第j个数与数组m的第i个数，当前者更大时，第k大数肯定不在数组m的前i个数中，去掉这i个数，求新数组的第k-i大的数；否则可去掉数组n的前j个数，求新数组的第k-j大的数。由于数组长度渐短，且k以1/2的阶递减，所以复杂度为O(log(m+n))。*/class Solution {public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n=nums1.size(); int m=nums2.size(); if((m+n)%2==1) return find_kth_of_sorted_arrays(nums1.begin(),nums1.size(),nums2.begin(),nums2.size(),(m+n+1)/2); int a=find_kth_of_sorted_arrays(nums1.begin(),nums1.size(),nums2.begin(),nums2.size(),(m+n)/2); int b=find_kth_of_sorted_arrays(nums1.begin(),nums1.size(),nums2.begin(),nums2.size(),(m+n+2)/2); return (a+b)/2.0; } int find_kth_of_sorted_arrays(vector<int>::iterator nums1,int n,vector<int>::iterator nums2,int m,int k){ //求第k大的数 if(m>n) return find_kth_of_sorted_arrays(nums2,m,nums1,n,k); if(m==0) return nums1[k-1]; if(k==1) return nums1[0]<nums2[0]?nums1[0]:nums2[0]; int i=m<k/2?m:k/2; int j=k-i; if(nums1[j-1]<nums2[i-1]) return find_kth_of_sorted_arrays(nums1+j,n-j,nums2,i,k-j); else return find_kth_of_sorted_arrays(nums1,j,nums2+i,m-i,k-i); }};新闻热点
疑难解答
