How to find the median of two sorted arrays efficiently?

本文共计211个文字，预计阅读时间需要1分钟。

java/** * 寻找两个有序数组的中位数 * 给定两个大小分别为m和n的有序数组nums1和nums2，找出这两个数组的中位数。 * 总体时间复杂度应为O(log(m+n))。 * @param nums1 数组1 * @param nums2 数组2 */

MedianofTwoSortedArrays.java

/** * 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)). * @param nums1 * @param nums2 * @return */ public static double findMedianSortedArrays(int[] nums1, int[] nums2) { int nums1Length = nums1.length; int nums2Length = nums2.length; int newSoretedNumsLength = nums1Length + nums2Length; int[] newSortedNums = new int[newSoretedNumsLength]; int n1Index = 0; int n2Index = 0; int newIndex = 0; while(n1Index =n2){ min = n2; n2Index ++; }else{ min = n1; n1Index ++; } if(newIndex >= newSoretedNumsLength){ break; } newSortedNums[newIndex] = min; newIndex ++; } double result = 0; if (newSoretedNumsLength%2==0) { int medianIndex = newSoretedNumsLength/2; result = (newSortedNums[medianIndex] + newSortedNums[medianIndex-1]) /2.0; } else { result = newSortedNums[newSoretedNumsLength/2]; } return result; }