LeetCode:Median of Two Sorted Arrays-白红宇

LeetCode:Median of Two Sorted Arrays

阅读量：5216 次

发布时间：2019-06-14

本文共 9328 字，大约阅读时间需要 31 分钟。

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)).

求两个有序数组的中位数，如果总元素个数是偶数，中位数是中间两个元素的平均值

详细讲解请参考我的另一篇博文：，那篇博文中如果数组总元素个数是偶数，求的是上中位数。

对于那篇博文中的算法2，这一题不能简单的套用，因为如果按照算法2的删除规则，当元素个数是偶数时，有可能把某个中位数删除了，比如对于数组【3,4】，【1,2,5,6】，比较4、5后就会把第一个数组中的3删除，但是3是要参与中位数的计算的。因此对于偶数个数的数组，我们加了一些判断，但是很复杂，代码如下，这里不推荐这种做法

1 class Solution { 2 public: 3     double findMedianSortedArrays(int A[], int m, int B[], int n) { 4         int mid_a = m/2, mid_b = n/2; 5         if(m == 0) 6         { 7             if(n % 2 == 0) 8                 return (B[mid_b] + B[mid_b-1]) / 2.0; 9             else return B[mid_b];10         }11         else if(n == 0)12         {13             if(m % 2 == 0)14                 return (A[mid_a] + A[mid_a-1]) / 2.0;15             else return A[mid_a];16         }17     18         if(m == 1)19         {20             if(n == 1)21                 return (A[0] + B[0]) / 2.0;22             if(n % 2 == 0)23             {24                 if(A[0] >= B[mid_b])25                     return B[mid_b];26                 else if(A[0] <= B[mid_b-1])27                     return B[mid_b-1];28                 else return A[0];29             }30             else31             {32                 if(A[0] >= B[mid_b+1])33                     return (B[mid_b] + B[mid_b+1]) / 2.0;34                 else if(A[0] <= B[mid_b-1])35                     return (B[mid_b] + B[mid_b-1]) / 2.0;36                 else return(B[mid_b] + A[0]) / 2.0;37             }38         }39         else if(n == 1)40         {41             if(m % 2 == 0)42             {43                 if(B[0] >= A[mid_a])44                     return A[mid_a];45                 else if(B[0] <= A[mid_a-1])46                     return A[mid_a-1];47                 else return B[0];48             }49             else50             {51                 if(B[0] >= A[mid_a+1])52                     return (A[mid_a] + A[mid_a+1]) / 2.0;53                 else if(B[0] <= A[mid_a-1])54                     return (A[mid_a] + A[mid_a-1]) / 2.0;55                 else return(A[mid_a] + B[0]) / 2.0;56             }57         }58         59         bool flag = false;60         if(m == 2 && n%2 == 0)61         {62                 if(A[0] <= B[0] && A[1] >= B[n-1])63                     return (B[mid_b] + B[mid_b-1]) / 2.0;64                 else if(A[0] >= B[0] && A[1] <= B[n-1])65                     return findMedianSortedArrays(A, m, &B[1], n-2);66                 flag = true;67         }68         else if(n == 2 && m%2 == 0)69         {70                 if(B[0] <= A[0] && B[1] >= A[m-1])71                     return (A[mid_a] + A[mid_a-1]) / 2.0;72                 else if(B[0] >= A[0] && B[1] <= A[m-1])73                     return findMedianSortedArrays(&A[1], m-2, B, n);74                 flag = true;75         }76         77     78             int cutLen = mid_a > mid_b ? mid_b:mid_a;79             if(m%2 == 0 && n%2 == 0 && flag == false)cutLen--;80             if(A[mid_a] == B[mid_b])81             {82                 if(m%2 == 0 && n%2 == 0)83                     return (A[mid_a] + max(A[mid_a-1], B[mid_b-1])) / 2.0; 84                 else 85                     return (A[mid_a] + B[mid_b]) / 2.0;86             }87             else if(A[mid_a] < B[mid_b])88                 return findMedianSortedArrays(&A[cutLen], m - cutLen, B, n - cutLen);89             else return findMedianSortedArrays(A, m - cutLen, &B[cutLen], n-cutLen);90         91     }92 };

View Code

我们可以对那篇博客中算法2稍作修改就可以求下中位数，因此当两个数组总元素时偶数时，求上中位数和下中位数，然后求均值

1 class Solution {  2 public:  3     double findMedianSortedArrays(int A[], int m, int B[], int n) {  4         int mid_a = m/2, mid_b = n/2;  5         if(m == 0)  6         {  7             if(n % 2 == 0)  8                 return (B[mid_b] + B[mid_b-1]) / 2.0;  9             else return B[mid_b]; 10         } 11         else if(n == 0) 12         { 13             if(m % 2 == 0) 14                 return (A[mid_a] + A[mid_a-1]) / 2.0; 15             else return A[mid_a]; 16         } 17          18         if((m+n) % 2) 19             return helper_up(A, m, B, n); 20         else return (helper_up(A, m, B, n) + helper_down(A, m, B, n)) / 2.0; 21     } 22     int helper_up(int A[], int m, int B[], int n) 23     { 24         int mid_a = m/2, mid_b = n/2; 25         if(m == 1) 26         { 27             if(n == 1) 28                 return A[0] < B[0] ? B[0] : A[0]; 29             if(n % 2 == 0) 30             { 31                 if(A[0] >= B[mid_b]) 32                     return B[mid_b]; 33                 else if(A[0] <= B[mid_b-1]) 34                     return B[mid_b-1]; 35                 else return A[0]; 36             } 37             else 38             { 39                 if(A[0] >= B[mid_b+1]) 40                     return B[mid_b+1]; 41                 else if(A[0] <= B[mid_b]) 42                     return B[mid_b]; 43                 else return A[0]; 44             } 45         } 46         else if(n == 1) 47         { 48             if(m % 2 == 0) 49             { 50                 if(B[0] >= A[mid_a]) 51                     return A[mid_a]; 52                 else if(B[0] <= A[mid_a-1]) 53                     return A[mid_a-1]; 54                 else return B[0]; 55             } 56             else 57             { 58                 if(B[0] >= A[mid_a+1]) 59                     return A[mid_a+1]; 60                 else if(B[0] <= A[mid_a]) 61                     return A[mid_a]; 62                 else return B[0]; 63             } 64         } 65         else 66         { 67             int cutLen = mid_a > mid_b ? mid_b:mid_a;//注意每次减去短数组的一半，如果数组长度n是奇数，一半是指n-1/2 68             if(A[mid_a] == B[mid_b]) 69                 return A[mid_a]; 70             else if(A[mid_a] < B[mid_b]) 71                 return helper_up(&A[cutLen], m - cutLen, B, n - cutLen); 72             else return helper_up(A, m - cutLen, &B[cutLen], n-cutLen); 73         } 74     } 75      76     int helper_down(int A[], int m, int B[], int n) 77     { 78         int mid_a = (m-1)/2, mid_b = (n-1)/2; 79         if(m == 1) 80         { 81             if(n == 1) 82                 return A[0] < B[0] ? A[0] : B[0]; 83             if(n % 2 == 0) 84             { 85                 if(A[0] >= B[mid_b+1]) 86                     return B[mid_b+1]; 87                 else if(A[0] <= B[mid_b]) 88                     return B[mid_b]; 89                 else return A[0]; 90             } 91             else 92             { 93                 if(A[0] >= B[mid_b]) 94                     return B[mid_b]; 95                 else if(A[0] <= B[mid_b-1]) 96                     return B[mid_b-1]; 97                 else return A[0]; 98             } 99         }100         else if(n == 1)101         {102             if(m % 2 == 0)103             {104                 if(B[0] >= A[mid_a+1])105                     return A[mid_a+1];106                 else if(B[0] <= A[mid_a])107                     return A[mid_a];108                 else return B[0];109             }110             else111             {112                 if(B[0] >= A[mid_a])113                     return A[mid_a];114                 else if(B[0] <= A[mid_a-1])115                     return A[mid_a-1];116                 else return B[0];117             }118         }119         else120         {121             int cutLen = (m/2 > n/2 ? n/2:m/2);//注意每次减去短数组的一半，如果数组长度n是奇数，一半是指n-1/2122             if(A[mid_a] == B[mid_b])123                 return A[mid_a];124             else if(A[mid_a] < B[mid_b])125                 return helper_down(&A[cutLen], m - cutLen, B, n - cutLen);126             else return helper_down(A, m - cutLen, &B[cutLen], n-cutLen);127         }128     }129 };

View Code

最优雅的方法是调用那篇博客中算法3求两个有序数组第k小元素的方法

1 class Solution { 2 public: 3     double findMedianSortedArrays(int A[], int m, int B[], int n) { 4         int mid_a = m/2, mid_b = n/2; 5         if(m == 0) 6         { 7             if(n % 2 == 0) 8                 return (B[mid_b] + B[mid_b-1]) / 2.0; 9             else return B[mid_b];10         }11         else if(n == 0)12         {13             if(m % 2 == 0)14                 return (A[mid_a] + A[mid_a-1]) / 2.0;15             else return A[mid_a];16         }17         18         if((m+n) % 2)19             return findKthSmallest(A, m, B, n, (m+n+1)/2);20         else return (findKthSmallest(A, m, B, n, (m+n)/2) + findKthSmallest(A, m, B, n, (m+n)/2+1)) / 2.0;21     }22     //找到两个有序数组中第k小的数,k>=123     int findKthSmallest(int vec1[], int n1, int vec2[], int n2, int k)24     {25         //边界条件处理26         if(n1 == 0)return vec2[k-1];27         else if(n2 == 0)return vec1[k-1];28         if(k == 1)return vec1[0] < vec2[0] ? vec1[0] : vec2[0];29         30         int idx1 = n1*1.0 / (n1 + n2) * (k - 1);31         int idx2 = k - idx1 - 2;32      33         if(vec1[idx1] == vec2[idx2])34             return vec1[idx1];35         else if(vec1[idx1] < vec2[idx2])36             return findKthSmallest(&vec1[idx1+1], n1-idx1-1, vec2, idx2+1, k-idx1-1);37         else38             return findKthSmallest(vec1, idx1+1, &vec2[idx2+1], n2-idx2-1, k-idx2-1);39     }40 };

转载于:https://www.cnblogs.com/TenosDoIt/p/3675220.html

你可能感兴趣的文章