2014
07-15

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

int A[] = {1,3,5,7,8};
int B[] = {4,7,8,10};

key = arr[m/2] = arr[2] = 5, 在数组B中查找key可得 r=0, 因为4是 小于等于key的最大元素。 key的最终排名即为 2+0+2 = 4.

#include <iostream>
using namespace std;

class Solution {
public:
double findMedianSortedArrays(int A[], int m, int B[], int n) {
if ((m+n) % 2 == 1)
return findkthElement(A, m, B, n, (m+n)/2+1);
else
return ( findkthElement(A, m, B, n, (m+n)/2) +
findkthElement(A, m, B, n, (m+n)/2+1)
) / 2.0;
}

int findkthElement(int A[], int m, int B[], int n, int k) {
if (m == 0) return B[k-1];
if (n == 0) return A[k-1];
if (k == 1) return min(A[0], B[0]);
if (m < n) return findkthElement(B, n, A, m, k);
int i = m/2;
int low = 0, high = n-1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (B[mid] <= A[i]) low = mid + 1; else high = mid - 1;
}
int j = high; //B[j] 是 <= A[i] 的那个最大的数

if (i+j+2 == k) //i+j+2 是 A[i] 在两个数组的 排名
return A[i];
else if (i+j+2 < k)
return findkthElement(A+i+1, m-i-1, B+j+1, n-j-1, k-i-j-2);
else
return findkthElement(A, i, B, j+1, k);
}
};

int main(){
Solution s;
int A[] = {1,3,5,7,8};
int B[] = {4,7,8,10};
int m = sizeof(A)/ sizeof(A[0]);
int n = sizeof(B)/sizeof(B[0]);
int ran = s.findkthElement(A, m, B,n, 6);
cout << ran << endl;
return 0;
}

1. #include <stdio.h>
int main()
{
int n,p,t[100]={1};
for(int i=1;i<100;i++)
t =i;
while(scanf("%d",&n)&&n!=0){
if(n==1)
printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
else {
if(n%4) p=n/4+1;
else p=n/4;
int q=4*p;
printf("Printing order for %d pages:n",n);
for(int i=0;i<p;i++){
printf("Sheet %d, front: ",i+1);
if(q>n) {printf("Blank, %dn",t[2*i+1]);}
else {printf("%d, %dn",q,t[2*i+1]);}
q–;//打印表前
printf("Sheet %d, back : ",i+1);
if(q>n) {printf("%d, Blankn",t[2*i+2]);}
else {printf("%d, %dn",t[2*i+2],q);}
q–;//打印表后
}
}
}
return 0;
}

2. 有限自动机在ACM中是必须掌握的算法，实际上在面试当中几乎不可能让你单独的去实现这个算法，如果有题目要用到有限自动机来降低时间复杂度，那么这种面试题应该属于很难的级别了。