題目
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
分析 兩個數(shù)組是有序的，要求中位數(shù)，若用歸并排序把兩個數(shù)組歸并起來，再求出中位數(shù)，這樣的時間復雜度是O(n+m)，所以嚴格來說會超時。 其實這個可以轉化為求第k大的元素的問題。
基本思想： 基本思想可以看這篇文章 比較a[k/2-1]與b[k/2-1]的大小，如果相等，那么容易知道該元素就是第k大的元素。 如果a[k/2-1]>b[k/2-1]，那么可以舍棄b數(shù)組的前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; } } //這里要舍棄的元素都是在數(shù)組的前面，所以設置一個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]; } } }新聞熱點
疑難解答
