4. 寻找两个正序数组的中位数---这题目没有解决，待研究

我就是我 2023-02-13 11:04 55阅读 0赞

# 题目来源 #

[LEETCODE][]

# 题目解析 #

中位数： 如果某个有序数组长度是奇数，那么其中位数就是最中间那个，如果是偶数，那么就是最中间两个数字的平均值

## 合并取中 ##

*  先将两个数组合并，两个有序数组的合并也是归并排序中的一部分。然后根据奇数，还是偶数，返回中位数
    
    时间复杂度：遍历全部数组 (m+n)  
    空间复杂度：开辟了一个数组，保存合并后的两个数组 O(m+n)
 *  小心细节，很容易出错

class Solution {
        
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
                    int m = nums1.length;
            int n = nums2.length;
    
    
            int[] arr = new int[m + n];
            int count = 0;
            int i = 0, j = 0;
            while (count != m + n){
        
                if (i == m){
        
                    while (j < n){
        
                        arr[count++] = nums2[j++];
                    }
                    break;
                }
    
                if (j == n){
        
                    while (i < m){
        
                        arr[count++] = nums1[i++];
                    }
                    break;
                }
                if (nums1[i] < nums2[j]){
        
                    arr[count++] = nums1[i++];
                }else{
        
                    arr[count++] = nums2[j++];
                }
            }
    
            if (count %2 != 0){
        
                return arr[count/2];
            }else {
        
                return (arr[count/2-1] + arr[count/2])/2.0;
            }
        }
    }

![在这里插入图片描述][20200528133036856.png]

## 双指针 ##

[LEETCPDE][]

*  不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
 *  tick：不需要区分m+n是奇数还是偶数：分别找第 (m+n+1) / 2 个，和 (m+n+2) / 2 个，然后求其平均值即可，这对奇偶数均适用。若 m+n 为奇数的话，那么其实 (m+n+1) / 2 和 (m+n+2) / 2 的值相等，相当于两个相同的数字相加再除以2，还是其本身。

class Solution {
        
        public double findMedianSortedArrays(int[] A, int[] B) {
        
        int m = A.length;
        int n = B.length;
        int len = m + n;
        int left = -1, right = -1;
        int aStart = 0, bStart = 0;
        for (int i = 0; i <= len / 2; i++) {
        
            left = right;
            if (aStart < m && (bStart >= n || A[aStart] < B[bStart])) {
        
                right = A[aStart++];
            } else {
        
                right = B[bStart++];
            }
        }
        if ((len & 1) == 0)
            return (left + right) / 2.0;
        else
            return right;
    }

[LEETCODE]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
[20200528133036856.png]: https://img-blog.csdnimg.cn/20200528133036856.png
[LEETCPDE]: https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by-w-2/