首页 > 学院 > 开发设计 > 正文

Leetcode: Median of Two Sorted Arrays

2019-11-14 21:11:07
字体:
来源:转载
供稿:网友
Leetcode: Median of Two Sorted Arrays
There are two sorted arrays A and B 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)).

For example, supposing the total length of two arrays is N. If N is an odd number, we need to find the N / 2 + 1 th number in two arrays, otherwise we need to find N / 2 th and N / 2 + 1 th number and return the average ofthem.

第二遍做的思路,参考了code Ganker的想法,问题等价于求两个array的第k个(这道题k = (m + n) / 2, 假设m和n分别是两个数组的元素个数,且从第1大的数开始)大的数是多少。基本思路是每次通过查看两个数组的第k/2大的数(是A[k/2-1],B[k/2-1]),如果A[k/2-1]=B[k/2-1],说明当前这个数即为两个数组剩余元素的第k大的数,如果A[k/2-1]>B[k/2-1], 那么说明B的前k/2个元素都不是我们要的第k大的数(原因:反证法,如果B的第k/2大的数是两个数组第k大的数,那么这k个数,B已经提供了k/2个,所以A也要提供k/2个,那么A[k/2-1]也在被提供之列。但A[k/2-1]>B[k/2-1], 所以A[k/2-1]才是两个数组第k大的数,与之前假设B[k/2-1]是第k大的数矛盾),反之则排除A的前k/2个,如此每次可以排除k/2个元素,最终k=1、或者m或者n小的那个变成0时,即达到base case。总的时间复杂度为O(logk),空间复杂度也是O(logk),即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。

 1 public class Solution { 2     public double findMedianSortedArrays(int A[], int B[]) { 3         if((A.length+B.length)%2==1) 4             return helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1); 5         else 6             return (helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2)   7                    +helper(A,B,0,A.length-1,0,B.length-1,(A.length+B.length)/2+1))/2.0; 8     } 9     10     PRivate int helper(int A[], int B[], int i, int i2, int j, int j2, int k)11     {12         int m = i2-i+1;13         int n = j2-j+1;14         if(m>n)15             return helper(B,A,j,j2,i,i2,k);16         if(m==0)17             return B[j+k-1];18         if(k==1)19             return Math.min(A[i],B[j]);20         int posA = Math.min(k/2,m);21         int posB = k-posA;22         if(A[i+posA-1]==B[j+posB-1])23             return A[i+posA-1];24         else if(A[i+posA-1]<B[j+posB-1])25             return helper(A,B,i+posA,i2,j,j2,k-posA);26         else27             return helper(A,B,i,i2,j+posB,j2,k-posB);28     }29 }

看以下这个别人的解法也许更好懂一点:

在计算中位数Median时候,需要根据奇偶分类讨论。

解决此题的方法可以依照:寻找一个unioned sorted array中的第k大(从1开始数)的数。因而等价于寻找并判断两个sorted array中第k/2(从1开始数)大的数。

特殊化到求median,那么对于奇数来说,就是求第(m+n)/2+1(从1开始数)大的数。

而对于偶数来说,就是求第(m+n)/2大(从1开始数)和第(m+n)/2+1大(从1开始数)的数的算术平均值。

那么如何判断两个有序数组A,B中第k大的数呢?

我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1],那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数,所以需要舍弃这一半,继续从A[k/2]到A[A.length-1]继续找。当然,因为这里舍弃了A[0]到A[k/2-1]这k/2个数,那么第k大也就变成了,第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1],就做之前对称的操作就好。

这样整个问题就迎刃而解了。

当然,边界条件页不能少,需要判断是否有一个数组长度为0,以及k==1时候的情况。

因为除法是向下取整,并且页为了方便起见,对每个数组的分半操作采取:

int partA = Math.min(k/2,m);int partB = k - partA;

为了能保证上面的分半操作正确,需要保证A数组的长度小于B数组的长度。

同时,在返回结果时候,注意精度问题,返回double型的就好。

 1 public class Solution {  2     public double findMedianSortedArrays(int A[], int B[]) {  3         int m = A.length;   4         int n = B.length;  5         int total = (m+n);  6         if(total%2 == 0){  7             double x = findKth(A,0,m-1,B,0,n-1,total/2);  8             double y = findKth(A,0,m-1,B,0,n-1,total/2+1);  9             return (x+y)/2.0; 10         }else{ 11             return findKth(A,0,m-1,B,0,n-1,total/2+1); 12         } 13     } 14      15     public double findKth(int[] A, int astart, int aend, int[] B, int bstart, int bend, int k){ 16         int m = aend-astart+1; 17         int n = bend-bstart+1; 18          19         if(m>n){ 20             return findKth(B,bstart,bend,A,astart,aend,k); 21         } 22          23         if(m == 0 ){ 24             return B[bstart+k-1]; //这里B[k-1]也是对的,不懂?估计跟B的长度总是调成最长的那个有关25         } 26          27         if(k==1){ 28             return Math.min(A[astart],B[bstart]); 29         } 30  31         int partA = Math.min(m,k/2); 32         int partB = k-partA; 33         if(A[astart+partA-1]<B[bstart+partB-1]){ 34             return findKth(A,astart+partA, aend, B, bstart, bend, k-partA); 35         }else if(A[astart+partA-1]>B[bstart+partB-1]){ 36             return findKth(A,astart, aend, B, bstart+partB, bend, k-partB); 37         }else{ 38             return A[astart+partA-1]; 39         } 40          41     } 42 }


发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表