📃 题目描述

题目链接：4. 寻找两个正序数组的中位数 (opens new window)

🔔 解题思路

可以直接看官方题解：https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/

• 要找到有序数组 nums1 和 nums2 的第 k 小的元素，我们可以比较 nums1[k/2 - 1] 和 nums2[k/2 -1]。nums1[k/2 - 1] 和 nums2[k/2 - 1] 的前面（不包括他们本身）都有 k/2 - 1 个元素
• 对于 nums1[k/2 - 1] 和 nums2[k/2 - 1] 中的最小值，最多会有 (k/2 - 1) + (k/2 - 1) = k - 2 个元素比他小，那么他就肯定不是第 k 小的数了！

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        // 奇数, 中位数是第 len/2 + 1 个数
        if (len % 2 == 1) {
            int k = len / 2 + 1;
            return findK(nums1, nums2, k);
        }
        // 偶数，中位数是第 len/2 和 第 len/2 + 1 个数
        int k1 = len / 2;
        int k2 = len / 2 + 1;
        return (findK(nums1, nums2, k1) + findK(nums1, nums2, k2)) / 2;
    }

    // 返回 nums1 和 nums2 中第 k 小的数的值
    private double findK(int[] nums1, int[] nums2, int k) {
        // nums1 的下标
        int index1 = 0;
        // nums2 d
        int index2 = 0;
        
        while (true) {
            // nums1 为空，直接 nums2 的第 k 个数就行
            if (index1 == nums1.length) {
                return nums2[index2 + k - 1];
            }
            // nums2 为空，直接 nums1 的第 k 个数就行
            if (index2 == nums2.length) {
                return nums1[index1 + k - 1];
            }
            if (k == 1) {
                return Math.min(nums1[index1], nums2[index2]);
            }

            // nums1 和 nums2 分别取 k/2 个数
            int half = k / 2;
            // nums1[index1, newIndex1]
            int newIndex1 = Math.min(index1 + half - 1, nums1.length - 1);
            // nums2[index2, newIndex2]
            int newIndex2 = Math.min(index2 + half - 1, nums2.length - 1);

            if (nums1[newIndex1] <= nums2[newIndex2]) {
                // 第 k 小的数肯定不在 [index1, newIndex1]
                k -= newIndex1 - index1 + 1;
                index1 = newIndex1 + 1;
            } 
            else {
                // 第 k 小的数肯定不在 [index2, newIndex2]
                k -= newIndex2 - index2 + 1;
                index2 = newIndex2 + 1;
            }
        }

    }
}

💥 复杂度分析

• 空间复杂度：O(1)
• 时间复杂度：O(LogN)