算法-寻找两个有序数组的中位数

缺乏、安全感 2023-07-09 06:24 28阅读 0赞

# 算法-寻找两个有序数组的中位数 #

# 1 概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/median-of-two-sorted-arrays/

## 1.2 题目描述 ##

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]
    nums2 = [2]

则中位数是 2.0  
示例 2:

nums1 = [1, 2]
    nums2 = [3, 4]

则中位数是 `(2 + 3)/2 = 2.5`

# 2 题解 #

## 2.1 解题思路 ##

1.  从较少数的数组m中取i个数，从较多数的数组n中取j个数(j=half-i,half=(n+m+1)/2 表示取一半数（偶数时为一半数，奇数为中间数）)
2.  考虑两个数组为
    
        0,1,...,i-1,i,...,m-1
        0,1,...,j-1,j,...,n-1
3.  然后设`l = 0, r = m`，分别表示选择`m`数组元素的个数的下界和上界
4.  设i表示取较少数的`m`数组元素的个数，`j=half-i`表示取较多数的`n`数组的个数，按以下规则判断
    
     *  如果发现`m[i-1]>n[j]`，就不满足中位数规则，需要取更多更大的`n`数组中的数，此时`r--`；
     *  如果发现`n[j-1]>m[i]`，就不满足中位数规则，需要取更多更大的`m`数组中的树，此时`l++`；
     *  递归上述过程，直到`l>r`或找到合适的`i`和`j`
5.  根据`i`和`j`的数值来决定最终取的中位数即可

这里以取的元素个数来考虑，而不是下标，更好应对边界条件。

## 2.2 代码 ##

class Solution{ 
        public double findMedianSortedArrays(int[] A, int[] B) { 
            int m = A.length;
            int n = B.length;
            int[] tmpA = A, tmpB = B;
            // shorter nums first
            if(m > n){ 
                tmpA = B;
                tmpB = A;
                m = tmpB.length;
                n = tmpA.length;
            }
            // half = (m + n + 1) / 2 = i + j
            int half = (m + n + 1) / 2;
    
            // represents the lower and upper bounds for selected elements num of tmpA
            int l = 0, r = m;
    
            // represents selected elements num for tmpA and tmpB
            int i=0,j=0;
    
            // shorter nums binary search
            while(l <= r){ 
                i = (l + r) / 2;
                j = half - i;
                if(i < m &&tmpB[j-1] > tmpA[i]){ 
                    // too small, tmpA right shift
                    l++;
                }else if(i > l && tmpA[i-1] > tmpB[j]){ 
                    // too big, tmpA left shift
                    r--;
                }else{ 
                    break;
                }
            }
            int maxLeft;
            if(i == 0){ 
                // only get elements from tmpB
                maxLeft = tmpB[j-1];
            }else if(j == 0){ 
                // only get elements from tmpA
                maxLeft = tmpA[i-1];
            }else{ 
                // get max
                maxLeft = Math.max(tmpB[j-1],tmpA[i-1]);
            }
            if((m+n) % 2 == 1){ 
                //odd, return
                return maxLeft;
            }
            // even,still need to find minRight
            int maxRight = 0;
            if(i == m){ 
                // we have got all elements from tmpA, and all of them is less than elements in tmpB
                // we need to take the element to the right of (j-1) -> j from tmpB
                maxRight = tmpB[j];
            }else if(j == n){ 
                // we have got all elements from tmpB, and all of them is less than elements in tmpA
                // we need to take the element to the right of (i-1) -> i from tmpA
                maxRight = tmpA[i];
            }else{ 
                // get min
                maxRight = Math.min(tmpB[j],tmpA[i]);
            }
            return (maxLeft + maxRight) / 2.0;
        }
    }

## 2.3 时间复杂度 ##

O(log(min(m,n)))

## 2.4 空间复杂度 ##

O(m+n)

## 2.5 注意事项 ##

不要使用  
`Arrays.sort(arr) Arrays.copyOf(arr, k)`等方法，  
面试官不会满意，同时有可能自己面试时可能忘记函数名。