package Solutions; public class Solution { public double findMedianSortedArrays(){ int[] nums1 = {1,3,6,8}; int[] nums2 = {2,4,7,9,10,15}; //为了使得分隔线在第二个数组的两侧都有元素,以至于不会出现访问时下标越界的情况 if (nums1.length>nums2.length){ //如果第一个数组长度大于第二个数组的长度 //则将较短的那个数组设置成第一个数组 int[] nums3 = nums1; nums1 = nums2; nums2 = nums3; } int m = nums1.length; int n = nums2.length; //分隔线左边的所有元素个数需要满足的个数 (m+n+1)/2 int totalLeft = (m+n+1)/2; //在nums1的区间[0,m]里查找恰当的分割线, //使得nums1[i-1] <= nums2[j] &&nums[j-1] <= nums1[i] int left = 0; int right = m; while (left<right){ int i = left+(right-left+1)/2; int j = totalLeft-i; if (nums1[i-1]>nums2[j]){ //下一轮搜索的区间[left,i-1] right = i-1; }else { //下一轮搜索的区间是[i,right] left = i; } } int i = left; int j = totalLeft-i; int nums1LeftMax = i == 0? Integer.MIN_VALUE : nums1[i-1]; int nums1RightMin = i == m? Integer.MAX_VALUE :nums1[i]; int nums2LeftMax = j == 0? Integer.MIN_VALUE : nums2[j-1]; int nums2RightMin = j == m? Integer.MAX_VALUE :nums2[j]; if ((m+n)%2==1){ return Math.max(nums1LeftMax,nums2LeftMax); }else { double a= (double) (Math.max(nums1LeftMax,nums2LeftMax)+Math.min(nums1RightMin,nums2RightMin))/2; System.out.println(a); return a; } } public static void main(String[] args) { Solution solution = new Solution(); solution.findMedianSortedArrays( ); } } |