leetcode练习题 median-of-two-sorted-arrays

解题思路

参考了讨论区的代码思路，若两个数组长度和为奇数则直接找中位数，长度和为偶数则取中间两个数的算术平均值。

寻找中位数主要是找第k个数的问题，首先保持短数组在前，若短数组的长度为0则第k个数只能在长数组中，返回长数组的第k个元素，若k为1且短数组长度不为0，则返回两个数组第一个元素的最小值。

假设两个数组的长度都大于等于k/2,若短数组的第k/2个元素的值小于长数组的第k/2个元素的值，则合并之后的数组中第k个元素一定不在短数组的前k/2个元素中，另一种不等情况也类似，相等的时候则直接返回第k/2个元素，实际的操作为取短数组长度和k/2的最小值，长数组的取k-该值，这样能保证总和是k个数，因为有可能短数组的元素个数少于k / 2。整个过程通过递归完成。

代码

class Solution {
public:double findres(int A[],int m,int B[],int n,int k){if(m > n)return findres(B,n,A,m,k);if(m == 0)return B[k - 1];if(k == 1)return A[0] > B[0] ? B[0] : A[0];int pa = k / 2 > m ? m : k / 2;int pb = k - pa;if(A[pa - 1] > B[pb - 1])return findres(A,m,B + pb,n - pb,k - pb);else if(A[pa - 1] < B[pb - 1])return findres(A + pa,m - pa,B,pb,k - pa);elsereturn A[pa - 1];}double findMedianSortedArrays(int A[], int m, int B[], int n) {int total = m + n;if(total % 2 == 1)return findres(A,m,B,n,total / 2 + 1);elsereturn (findres(A,m,B,n,total / 2) + findres(A,m,B,n,total / 2 + 1)) / 2;}
};