4.两个排序数组的中位数

哈哈哈哈刚发现leetcode还有中文版的，叫领扣，不用翻译了

There are two sorted arrays nums1 and nums2 of size m and n respectively.
给出两个有序数组nums1和nums2，长度分别为m和n

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
找出所有元素中位数，时间复杂度需要为O(log (m+n))

举例1:

nums1 = [1, 3]
nums2 = [2]
中位数为2.0

举例2:

nums1 = [1, 2]
nums2 = [3, 4]
中位数为(2 + 3)/2 = 2.5

拟采用方法：
A，B数组，记录A，B当前起始序号，每次分别二分，取得中间值mid1和mid2。则得到（假设mid1>mid2）比mid2小的一部分，比mid1大的一部分，以及mid1和mid2中间的一部分共三部分。
根据所要找的排名k，删除某两部分，最终找到需求。

照着上面的拟采用方法写了很久，发现简单的测试样例就会出错。重新思考了一下发现是整个思路存在问题

1               2 
A_left  A_mid   A_right
3         ^     4
B_left  B_mid   B_right

块1和块3确实小于块4
块2和块4确实大于块1
但是块1并不是全局最小的块，因为块3可能存在更小取值

改进方法为：

1               2 
A_left  A_i     A_right
3               4
B_left  B_j     B_right

j由i的取值计算得到，i + j = target。若此时满足块1整体小于块4，块3整体小于块2，则问题得解
否则对块A进行二分，重新确定i和j

具体代码：

#include<vector>
#include<ctype.h>
#include<stdio.h>
#include<cstdio>
#include<iostream>

using namespace std;


int findtarget(vector<int>& nums1, vector<int>& nums2, int target){
    cout << "it is target : " << target << endl;
    int i,j,ai,bj,ao,bo;
    int move = (nums1.size() - 1) / 2;
    move = ((move + 1) / 2)?((move + 1 )/ 2 ):1;
    if(target == 1){
        if(nums1.size() == 0){
            return nums2[0];
        }
        if(nums2.size() == 1){
            return (nums1[0] > nums2[0])?(nums2[0]):(nums1[0]);
        }
        if(nums1[0] < nums2[0]){
            return nums2[0];
        }
        if(nums1[0] > nums2[1]){
            return nums2[1];
        }
        return nums1[0];
        
    }
    
    i = (nums1.size() - 1) / 2;
    j = target - 2 - i;
    
    ai = (i>=0)?nums1[i]:0;
    bj = nums2[j]; 
    
    ao = (i >= nums1.size() - 1)?(bj + 1):nums1[i+1];
    bo = (j >= nums2.size() - 1)?(ai + 1):nums2[j+1];
    
    while(i >= 0 && j >= 0 &&(ao < bj || bo < ai)){
        if(bo < ai){
            i = (i>0)?((i - move >= 0)?(i-move):0):(-1);
        }
        else if(ao < bj){
            i = (i>=0)?((i + move >= nums1.size())?(nums1.size()-1):(i+move)): (-1);
        }
        j = target - 2 - i;
        ai = (i>=0)?nums1[i]:ai;
        bj = (j>=0)?nums2[j]:bj;
        ao = (i >= nums1.size() - 1)?(bj + 1):nums1[i+1];
        bo = (j >= nums2.size() - 1)?(ai + 1):nums2[j+1];
        move = (move + 1) / 2;
    }
    cout << "i:" << i << "  j:" << j << endl;
    if(i < 0){
        return nums2[target - 1];
    }
    if(j < 0){
        return nums1[target - 1];
    }
    return (nums1[i] > nums2[j])? (nums1[i]) : (nums2[j]);
}


double find(vector<int>& nums1, vector<int>& nums2){
    if(nums1.size() > nums2.size()){
        return find(nums2, nums1);
    }
    int num_sum = nums1.size() + nums2.size();
    int target = (num_sum + 1) / 2;
    cout << nums1.size() << " -one " << nums2.size() << " two" << "  ??" <<endl; 
    int result = findtarget(nums1, nums2, target);
    double res = result;
    cout << result << endl;
    if(num_sum % 2 == 0){
        result += findtarget(nums1, nums2, target + 1);
        cout << result - res << endl;
        res = result / 2.0 ;
    }
    return res;
} 

int main(){
    int a[10] = {1,4};
    int b[10] = {2,3};
    vector<int> nums1(a,a+2);
    vector<int> nums2(b,b+2);
    double res = find(nums1, nums2);
    cout << "result is:" << res << endl;
    return 0;
}