leetcode의 Median of Two Sorted Arrays

Median of Two Sorted Arrays
There are two sorted arrays A and B 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)).
사고방식: 먼저 중위수가 몇 번째 수인지 판단한 다음에 중위수의 개수를 2로 나누어 절반은 A에서, 절반은 B에서, 만약에 A[mid]class Solution { public: int find(int a[],int m,int b[],int n,int index) { if(m==0)return b[index-1]; if(n==0)return a[index-1]; if(index==1)return(a[0]<b[0]?a[0]:b[0]); int mid = index / 2;// , if(min(m,n)<mid)mid = min(m,n); if(a[mid-1] < b[mid-1])return find(a+mid,m-mid,b,n,index-mid); else return find(a,m,b+mid,n-mid,index-mid); } double findMedianSortedArrays(int A[], int m, int B[], int n) { int mid = (m+n+1)/2;// double temp = find(A,m,B,n,mid); if((m+n)&0x1==1)return temp; else return (temp+find(A,m,B,n,mid+1))/2.0;// , } };

좋은 웹페이지 즐겨찾기