leetcode刷题（数组）5—寻找两个正序数组的中位数

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

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。

分析：

class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int m = nums1.length; int n = nums2.length; int res1 = 0,res2 = 0; double res = 0; //第一个寻找的数是第几小的,eg:一共7个数，tar1 = 4 ,tar2 = 4;一共8个数，tar1 = 4 ,tar2 = 5; int tar1 = (m + n + 1)/2; //第二个 int tar2 = (m + n + 2)/2; res1 = findKthSortedArrays(nums1, 0, nums2, 0, tar1); res2 = findKthSortedArrays(nums1, 0, nums2, 0, tar2); res = (res1 + res2)/2.0; return res; } //两数组中找第K个大的数 public int findKthSortedArrays(int[] nums1,int fir1, int[] nums2,int fir2,int k){ int m = nums1.length; int n = nums2.length; int res = 0; if(fir1 == m || fir2 == n){ res = fir1 == m ? nums2[fir2 + k - 1] : nums1[fir1 + k - 1]; return res; } if(k == 1){ res = nums1[fir1] < nums2[fir2] ? nums1[fir1] : nums2[fir2]; return res; } int tar = k / 2; if(fir1 + tar - 1 >= m || fir2 + tar - 1 >= n){ tar = Math.min(m - fir1 ,n - fir2); } res = nums1[fir1 + tar - 1] < nums2[fir2 + tar - 1] ? findKthSortedArrays(nums1, fir1 + tar, nums2, fir2, k - tar) : findKthSortedArrays(nums1, fir1, nums2, fir2 + tar, k - tar); return res; } }