sinat_28942275的博客

原创 Leetcode:寻找两个正序数组的中位数

题目： 给定两个排序数组，求其中位数。要求时间复杂度O(log(m+n))。 解析： 记数组1大小m，数组2大小n，那么中位数为合并后的排序数组的最中间两个数字nums[mid1] nums[mid2]的平均值，或者最中间的那个数字nums[mid1]。使用两个指针i,j遍历每个数组，判断其数字nums1[i]和nums2[j]大小，小的作为合并后数组的当前值，用一个变量index记录合并后数组的索引。若一个数组遍历完，则遍历剩余的数组，否则比较当前值，当index=mid1和mid2时，记录两个值。暂时实