Leetcode-Median of Two Sorted Arrays

#Leetcode

题目描述

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)).

AC代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <cstdio>


using namespace std;

double findKth(int A[], int m, int B[], int n, int k)
{
    	if(m > n)
    		return findKth(B,n,A,m,k);
    	if(m == 0)
    		return B[k - 1];
    	if(k <= 1)
    		return min(A[0], B[0]);
    
    	int pa = min(k / 2, m), pb = k - pa;
    	if(A[pa - 1] < B[pb - 1])
    		return findKth(A + pa, m - pa, B, n, k - pa);
    	else if(A[pa - 1] > B[pb - 1])
    		return findKth(A, m, B + pb, n - pb, k - pb);
    	else
    		return A[pa - 1];
    }
    
    double findMedianSortedArrays(int A[], int m, int B[], int n)
    {
    	int k = m + n;
    	if(k & 0x1)
    		return findKth(A, m, B, n, k / 2 + 1);
    	else
    		return (findKth(A, m, B, n, k / 2) + findKth(A, m, B, n, k / 2 + 1)) / 2;
}

int main()
{
    #ifndef ok
    	freopen("in4.in", "r", stdin);
    	freopen("std4.out", "w", stdout);
    #endif
    
    	int m;
    	cin>>m;
    	int A[m];
    	for(int i = 0; i < m; i++)
    		cin>>A[i];
    	int n;
    	cin>>n;
    	int B[n];
    	for(int j = 0; j < n; j++)
    		cin>>B[j];
    //	cout<<(float)findMedianSortedArrays(A, m, B, n)<<endl;
    
    	printf("%.5f\n", findMedianSortedArrays(A, m, B, n));
    #ifndef ok
    	fclose(stdin);
    	fclose(stdout);
    #endif
    
    	return 0;
}