这道题最简单的思路是把两个数组合并起来,再排序,如果数组长度是奇数,return 中间的那个数,如果数组长度是偶数,return 中间两个数的平均值。时间复杂度 O(nlogn)用于数组排序。
public double findMedianSortedArrays(int[] nums1, int[] nums2) { int[] nums = new int[nums1.length+nums2.length]; int i=0; for(;i<nums1.length;i++){ nums[i]=nums1[i]; } for(int j=0;j<nums2.length;j++){ int n = nums.length; nums[i+j]=nums2[j]; } Arrays.sort(nums); int rest = nums.length%2; int index = nums.length/2; if(rest==1){ return nums[index]; } else{ return ((double)(nums[index-1]+nums[index])/2); } }
但是这道题的题目要求:The overall run time complexity should be O(log (m+n)),这两个数组是有序数组,看来不需要combine两个数组再排序。