3112、访问消失节点的最小时间

4、两个有序数组的中位数

---

给定两个大小为 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

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

题解

1、二分查找 划分数组

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 分别获得两个数字的长度
        int m = nums1.length;
        int n = nums2.length;
        // 第一个数组必须是元素较少的数组，否则交换
        if (m > n) {
            int[] tmp = nums1;
            nums1 = nums2;
            nums2 = tmp;
            m = m^n;
            n = n^m;
            m = m^n;
        }
        // 二分查找满足条件的中位数
        // 必须满足两个条件：1、左右两边的元素个数相等或者差一个元素
        // 对角元素小于等于关系，保证右半部分的最小值大于等于左半部分的最大值
        int iMin = 0,iMax = m,halfLen = (m + n + 1)/2;
        while(iMin <= iMax) {
            int i = (iMin + iMax)/2;
            int j = halfLen - i;// 保证j始终满足：j + i = m - i + n - j + 1; 
            if (i < iMax && nums2[j - 1] > nums1[i]) {
                iMin = i + 1; // i 太小
            } else if (i > iMin && nums1[i - 1] > nums2[j]) {
                iMax = i - 1; // i 太大
            } else { // 找到i了
                int maxLeft = 0;
                // 特殊情况处理
                if (i == 0) { maxLeft = nums2[j - 1]; }
                else if (j == 0) { maxLeft = nums1[i - 1];}
                else {
                    maxLeft = Math.max(nums1[i - 1],nums2[j - 1]);
                }
                // 总元素数量为奇数
                if ((m + n)%2 == 1) { return maxLeft;}
                
                int minRight = 0;
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    minRight = nums1[i];
                } else {
                    minRight = Math.min(nums1[i],nums2[j]);
                }
                // 总元素数量为偶数
                return (maxLeft + minRight) / 2.0;
            }
        }
        return 0.0;
    }
}

2、二分查找

两个有序数组，二分查找取中位数

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length;
        int totalLength = len1 + len2;
        if (totalLength % 2 == 1) {
            int midIndex = totalLength / 2;
            double median = getKthElement(nums1, nums2, midIndex + 1);
            return median;
        } else {
            int midIndex1 = totalLength / 2 - 1,midIndex2 = totalLength / 2;
            double median = (getKthElement(nums1,nums2,midIndex1 + 1) + getKthElement(nums1,nums2,midIndex2 + 1)) / 2.0;
            return median;
        }
    }
    // 获取两个有序数组，第K的元素
    private int getKthElement(int[] nums1,int[] nums2,int k) {
        int length1 = nums1.length,length2 = nums2.length;
        int index1 = 0,index2 = 0;
        int kthElement = 0;

        while (true) {
            // 边界情况
            if(index1 == length1) {
                return nums2[index2 + k - 1];
            }
            if (index2 == length2) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // 正常二分
            int half = k / 2;
            int newIndex1 = Math.min(index1 + half, length1) - 1;
            int newIndex2 = Math.min(index2 + half,length2) - 1;
            int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
            if (pivot1 <= pivot2) {
                // 排除一部分
                k -= (newIndex1 - index1 + 1);
                index1 = newIndex1 + 1;
            } else {
                // 排除一部分
                k -= (newIndex2 - index2 + 1);
                index2 = newIndex2 + 1;
            }
        }
    }
}

---

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com