寻找两个正序数组的中位数

问题

寻找两个正序数组的中位数 原题链接：https://leetcode.cn/problems/median-of-two-sorted-arrays?envType=study-plan-v2&envId=top-100-liked

解法

这题在我复习826数据结构专业课中，最后一章（排序）里面接触过，当时只是有一个大概得思想并未去实现它，如今第一次实现这个算法其中很多的细节我算是理清楚了，其中值得注意的点有：
int newIndexM=min(m-1,indexM+k/2-1);这行代码主要是避免数组取到的下标越界造成错误，因此取个min。

class Solution {
public:
    int m=0;
    int n=0;
    double findMedianSortedArraysK(vector<int>& nums1,vector<int>& nums2,int k){
        int indexM=0,indexN=0;//分别表示nums1和2的数组当前的下标
        while(1){
            if(indexM==m) return nums2[indexN+k-1];//数组nums1已经被耗完了
            if(indexN==n) return nums1[indexM+k-1];
            if(k==1) return min(nums1[indexM],nums2[indexN]);

            //找到中位数更新
            int newIndexM=min(m-1,indexM+k/2-1);//避免越界
            int newIndexN=min(n-1,indexN+k/2-1);
            int pivotM=nums1[newIndexM];
            int pivotN=nums2[newIndexN];
            if(pivotM<=pivotN){//小于那部分直接去掉
                k-=newIndexM-indexM+1;
                indexM=newIndexM+1;
            }else{
                k-=newIndexN-indexN+1;
                indexN=newIndexN+1;
            }
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        m=nums1.size();
        n=nums2.size();
        if((m+n)%2==1){
            return findMedianSortedArraysK(nums1,nums2,(m+n+1)/2);//默认下取整
        }else{
            return (findMedianSortedArraysK(nums1,nums2,(m+n)/2)+
                    findMedianSortedArraysK(nums1,nums2,((m+n)/2)+1))/2;
        }
    }
};