将找两个排序数组的中间值转换为找两个数组的第k小的数，findKthNumber是在两个数组中找第k小的数。
每次找k/2个数，如果一个数组最末尾那个小于另一个，那这个数组的前面部分肯定属于整个k/2里面。
start2 + mid + 1每次加了1，说明start1、start2都是新的数，属于当前的k的数，所以mid要用k/2减1，因为要计算当前start1、start2的数。
要考虑start1、start2越界的情况，同时当前计算，按照k/2找的新的数的索引，也要考虑越界的情况。
注意：start1、start2是比较的数字在两个数组中开始的下标(或者说索引，是从0开始到size()-1)，k代表个数，具体说是当前还需要几个数字。
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int length1 = nums1.size(); int length2 = nums2.size(); int len = length1 + length2; int mid = len/2; if(len % 2 == 0) return (findKthNumber(nums1,nums2,0,0,mid) + findKthNumber(nums1,nums2,0,0,mid+1))/2.0; else return findKthNumber(nums1,nums2,0,0,mid+1); } int findKthNumber(vector<int> nums1,vector<int> nums2,int start1,int start2,int k){ int length1 = nums1.size(); int length2 = nums2.size(); if(start1 >= length1) return nums2[start2+k-1]; if(start2 >= length2) return nums1[start1+k-1]; if(k == 1) return min(nums1[start1],nums2[start2]); int mid = k/2 - 1; int num1 = start1 + mid >= length1 ? 0x7FFFFFFF : nums1[start1 + mid]; int num2 = start2 + mid >= length2 ? 0x7FFFFFFF : nums2[start2 + mid]; if(num1 > num2) return findKthNumber(nums1,nums2,start1,start2 + mid + 1,k-k/2); else return findKthNumber(nums1,nums2,start1 + mid + 1,start2,k-k/2); } };
https://www.cnblogs.com/lupx/p/lupeixin.html
自己写了一遍：
注意findKth的k这个参数是个数，即前k个，而不是下标
class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int length1 = nums1.size(),length2 = nums2.size(); int start1 = 0,start2 = 0; int sum = length1 + length2; if(sum % 2) return findKth(nums1,nums2,start1,start2,sum/2 + 1); else return (findKth(nums1,nums2,start1,start2,sum/2) + findKth(nums1,nums2,start1,start2,sum/2 + 1))/2.0; } int findKth(vector<int> nums1,vector<int> nums2,int start1,int start2,int k){ if(start1 >= nums1.size()) return nums2[start2 + k - 1]; if(start2 >= nums2.size()) return nums1[start1 + k - 1]; if(k == 1) return min(nums1[start1],nums2[start2]); int mid = k/2; int value1 = start1 + mid - 1 >= nums1.size() ? INT_MAX : nums1[start1 + mid - 1]; int value2 = start2 + mid - 1 >= nums2.size() ? INT_MAX : nums2[start2 + mid - 1]; if(value1 < value2) return findKth(nums1,nums2,start1 + mid,start2,k - k/2); else return findKth(nums1,nums2,start1,start2 + mid,k - k/2); } };