题目
There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Example 1: nums1 = [1, 3] nums2 = [2] The median is 2.0 Example 2: nums1 = [1, 2] nums2 = [3, 4] The median is (2 + 3)/2 = 2.5
分析 两个数组是有序的，要求中位数，若用归并排序把两个数组归并起来，再求出中位数，这样的时间复杂度是O(n+m)，所以严格来说会超时。 其实这个可以转化为求第k大的元素的问题。
基本思想： 基本思想可以看这篇文章 比较a[k/2-1]与b[k/2-1]的大小，如果相等，那么容易知道该元素就是第k大的元素。 如果a[k/2-1]>b[k/2-1]，那么可以舍弃b数组的前k/2项元素了。反之同理。
代码： 借鉴了这篇文章
public class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { if ((n1 + n2) % 2 == 1) { return findNumK(nums1,0, nums2,0, (n1 + n2) / 2 + 1); } else { return (findNumK(nums1,0, nums2,0, (n1 + n2) / 2) + findNumK(nums1,0, nums2,0, (n1 + n2) / 2 + 1)) / 2; } } //这里要舍弃的元素都是在数组的前面，所以设置一个start来表示舍弃之后元素的起始下标 public double findNumK(int[] nums1,int start1, int[] nums2,int start2, int k) { int n1 = nums1.length - start1; int n2 = nums2.length - start2; if (n1 > n2) { return findNumK(nums2,start2, nums1,start1, k); } if (n1 == 0) { return nums2[start2 + k - 1]; } if (k == 1) { return Math.min(nums1[start1], nums2[start2]); } //把k分成两半 int temp1 = Math.min(k / 2, n1); int temp2 = k - temp1; if (nums1[temp1 + start1 - 1] < nums2[temp2 + start2 - 1]) { return findNumK(nums1,start1+temp1, nums2, start2, k - temp1); } else if (nums1[temp1 + start1 - 1] > nums2[temp2 + start2 - 1]) { return findNumK(nums1,start1, nums2,start2+temp2, k - temp2); } else { return nums1[temp1 - 1 +start1]; } } }新闻热点
疑难解答
