首页 > 代码库 > 4. Median of Two Sorted Arrays

4. Median of Two Sorted Arrays

2024-09-08 06:07:07   215人阅读

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

本题是我做过的比较难的题目了，看了答案也看了半天。即使是现在，也对于实现的细节有点不理解，一会再说不懂得地方。本题实现原理是，首先找出数组长度较小的数组放在函数参数前面的位置，
然后找出数组长度较大的数组放在函数参数后面的位置。然后分别找出小数组和大数组的中间的位置，设小数组为nums1[],大数组为nums2[],设i为小数组中间的位置，j为大数组中间的位置。
nums1[i-1]与nums2[j]进行比较，如果1>2，则需要将小数组的i往左移动，如果符合条件1，则在进行比较nums1[i]与nums2[j-1]进行比较，如果1<2，则将小数组的i往右移动，如果上述
两个条件都符合，则取nums1[i-1],nums2[j-1]的最大值；然后看两个数组的和是单数还是双数，如果是双数，再找nums1[i],nums2[j]的较小值，然后取平均数。代码如下：
 1 public class Solution {
 2     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 3         if(nums1.length>nums2.length) return findMedianSortedArrays(nums2,nums1);
 4         int m = nums1.length;
 5         int n = nums2.length;
 6         int minidx = 0;
 7         int maxidx = m;//??????
 8         int mid = (m+n+1)/2;//?????
 9         int num1 = 0;
10         int num2 = 0;
11         int i = 0;
12         int j = 0;
13         while(minidx<=maxidx)//?????
14         {
15             i = minidx+(maxidx-minidx)/2;
16             j = mid-i;
17             if(i>0&&j<n&&nums1[i-1]>nums2[j]) maxidx = i-1;
18             else if(i<m&&j>0&&nums1[i]<nums2[j-1]) minidx = i+1;
19             else{
20                 if(i==0) num1=nums2[j-1];
21                 else if(j==0) num1 =nums1[i-1];
22                 else num1 = Math.max(nums1[i-1],nums2[j-1]);
23                 break;
24             }
25         }
26         if(((m+n)&1)==1) return num1;
27         if(i==m) num2 = nums2[j];
28         else if(j==n) num2 = nums1[i];
29         else num2 = Math.min(nums1[i],nums2[j]);
30         return (num1+num2)/2.;
31     }
32 }

代码里面关于不懂的地方我都标记出来了，首先minidx为什么不为m-1，我想了一下，可能是要区别开数组为空和数组不为空的情况。还有为什么mid为（m+n+1）／2，原因是这里面不是按照索引进行找的，而是按照个数进行找的，简而言之，就是，不是从0开始，而是从1开始。还有就是不懂的地方了，为什么要minidx<=maxidx，这个部分有点难以理解？？？？？？？

4. Median of Two Sorted Arrays


联系
我们