寻找两个正序数组的中位数

题目要求

给定两个正序数组 nums1 和 nums2，其大小分别为 m 和 n。要求找出这两个数组合并后的中位数。要求算法的时间复杂度为 O(log(m+n))。

解题思路

要在 O(log(m+n)) 的时间复杂度内找到两个正序数组的中位数，可以使用二分查找的方法。以下是解题的步骤：

确定较短的数组：由于我们要进行二分查找，为了优化查找效率，我们应该在长度较短的数组上进行二分查找。假设 nums1 是较短的数组。
二分查找：在 nums1 上进行二分查找，找到一个位置 i，同时在 nums2 中找到位置 j，使得 nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。这意味着左半部分的所有元素都小于等于右半部分的所有元素。
处理边界情况：在二分查找过程中，需要处理 i 或 j 达到数组边界的情况。例如，当 i 为 0 时，说明中位数在 nums2 中；当 i 为 m 时，说明中位数在 nums1 中。
计算中位数：
- 如果 m + n 是奇数，中位数是左半部分的最大值。
- 如果 m + n 是偶数，中位数是左半部分的最大值和右半部分的最小值的平均值。
左半部分最大值和右半部分最小值的确定：
- 左半部分最大值是 max(nums1[i-1], nums2[j-1])。
- 右半部分最小值是 min(nums1[i], nums2[j])。
循环条件：二分查找的循环条件是 i 在 0 到 m 的范围内变化，通过比较 nums1[i-1]、nums1[i]、nums2[j-1] 和 nums2[j] 来调整 i 的值。

通过上述步骤，可以在 O(log(min(m,n))) 的时间复杂度内找到两个数组的中位数，满足题目要求的 O(log(m+n)) 时间复杂度。

Golang 版本

package main

import (
	"fmt"
	"math"
)

func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
	// 确保nums1是较短的数组
	if len(nums1) > len(nums2) {
		nums1, nums2 = nums2, nums1
	}

	m, n := len(nums1), len(nums2)
	imin, imax := 0, m
	halfLen := (m + n + 1) / 2

	for imin <= imax {
		i := (imin + imax) / 2
		j := halfLen - i

		if i < imax && nums2[j-1] > nums1[i] {
			// i 的值太小，增加它
			imin = i + 1
		} else if i > imin && nums1[i-1] > nums2[j] {
			// i 的值太大，减小它
			imax = i - 1
		} else {
			// i 的值刚好合适
			maxLeft := 0.0
			if i == 0 {
				maxLeft = float64(nums2[j-1])
			} else if j == 0 {
				maxLeft = float64(nums1[i-1])
			} else {
				maxLeft = math.Max(float64(nums1[i-1]), float64(nums2[j-1]))
			}

			if (m+n)%2 == 1 {
				// 如果总长度是奇数，中位数是左半部分的最大值
				return maxLeft
			}

			minRight := 0.0
			if i == m {
				minRight = float64(nums2[j])
			} else if j == n {
				minRight = float64(nums1[i])
			} else {
				minRight = math.Min(float64(nums1[i]), float64(nums2[j]))
			}

			// 如果总长度是偶数，中位数是左半部分的最大值和右半部分的最小值的平均值
			return (maxLeft + minRight) / 2.0
		}
	}

	return 0.0
}

func main() {
	nums1 := []int{1, 3}
	nums2 := []int{2}
	fmt.Println("The median is:", findMedianSortedArrays(nums1, nums2))
}

这段代码实现了上述描述的算法，通过二分查找在两个正序数组中找到中位数。在主函数 main 中，给出了两个数组的示例，并调用 findMedianSortedArrays 函数来计算并打印中位数。

C++版本

#include <iostream>
#include <vector>
#include <algorithm>

double findMedianSortedArrays(std::vector<int>& nums1, std::vector<int>& nums2) {
    if (nums1.size() > nums2.size()) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.size();
    int n = nums2.size();
    int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
    while (imin <= imax) {
        int i = (imin + imax) / 2;
        int j = halfLen - i;
        if (i < imax && nums2[j - 1] > nums1[i]) {
            imin = i + 1;
        } else if (i > imin && nums1[i - 1] > nums2[j]) {
            imax = i - 1;
        } else {
            int maxLeft = 0;
            if (i == 0) {
                maxLeft = nums2[j - 1];
            } else if (j == 0) {
                maxLeft = nums1[i - 1];
            } else {
                maxLeft = std::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 = std::min(nums1[i], nums2[j]);
            }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

int main() {
    std::vector<int> nums1 = {1, 3};
    std::vector<int> nums2 = {2};
    std::cout << "The median is: " << findMedianSortedArrays(nums1, nums2) << std::endl;
    return 0;
}

这段 C++代码实现了寻找两个正序数组的中位数的功能，它首先确保第一个数组是较短的数组，然后使用二分查找算法来找到正确的中位数。在 main 函数中，提供了两个数组的示例，并调用 findMedianSortedArrays 函数来计算并输出中位数。 ##Python 版本

def findMedianSortedArrays(nums1, nums2):
    # Make sure nums1 is the smaller array
    if len(nums1) > len(nums2):
        nums1, nums2 = nums2, nums1

    m, n = len(nums1), len(nums2)
    imin, imax = 0, m
    half_len = (m + n + 1) // 2

    while imin <= imax:
        i = (imin + imax) // 2
        j = half_len - i
        if i < m and nums2[j-1] > nums1[i]:
            imin = i + 1
        elif i > 0 and nums1[i-1] > nums2[j]:
            imax = i - 1
        else:
            # i is perfect
            if i == 0: max_of_left = nums2[j-1]
            elif j == 0: max_of_left = nums1[i-1]
            else: max_of_left = max(nums1[i-1], nums2[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            # i is not perfect, but can be corrected
            if i == m: min_of_right = nums2[j]
            elif j == n: min_of_right = nums1[i]
            else: min_of_right = min(nums1[i], nums2[j])

            return (max_of_left + min_of_right) / 2.0

    return -1

# Example usage:
nums1 = [1, 3]
nums2 = [2]
print("The median is:", findMedianSortedArrays(nums1, nums2))

这段 Python 代码实现了寻找两个有序数组的中位数的算法。它首先确保nums1是较短的数组，然后使用二分查找来找到中位数。在示例用法中，给出了两个数组，并调用findMedianSortedArrays函数来计算并打印中位数。 ##Java 版本

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length > nums2.length) {
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;
        }

        int m = nums1.length;
        int n = nums2.length;
        int imin = 0, imax = m, halfLen = (m + n + 1) / 2;
        while (imin <= imax) {
            int i = (imin + imax) / 2;
            int j = halfLen - i;
            if (i < imax && nums2[j-1] > nums1[i]){
                imin = i + 1;
            } else if (i > imin && nums1[i-1] > nums2[j]) {
                imax = i - 1;
            } else {
                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;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums1 = {1, 3};
        int[] nums2 = {2};
        System.out.println("The median is: " + solution.findMedianSortedArrays(nums1, nums2));
    }
}

这段 Java 代码实现了寻找两个有序数组的中位数的算法。它首先确保nums1是较短的数组，然后使用二分查找来找到中位数。在main方法中，创建了一个Solution对象，并给出了两个数组的示例，调用findMedianSortedArrays方法来计算并打印中位数。 ##Rust 版本

fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
    let (mut nums1, mut nums2) = if nums1.len() <= nums2.len() {
        (nums1, nums2)
    } else {
        (nums2, nums1)
    };

    let (m, n) = (nums1.len(), nums2.len());
    let mut imin = 0;
    let mut imax = m;
    let half_len = (m + n + 1) / 2;

    while imin <= imax {
        let i = (imin + imax) / 2;
        let j = half_len - i;
        if i < imax && nums2[j - 1] > nums1[i] {
            imin = i + 1;
        } else if i > imin && nums1[i - 1] > nums2[j] {
            imax = i - 1;
        } else {
            let max_left = if i == 0 {
                nums2[j - 1] as f64
            } else if j == 0 {
                nums1[i - 1] as f64
            } else {
                nums1[i - 1].max(nums2[j - 1]) as f64
            };

            if (m + n) % 2 == 1 {
                return max_left;
            }

            let min_right = if i == m {
                nums2[j] as f64
            } else if j == n {
                nums1[i] as f64
            } else {
                nums1[i].min(nums2[j]) as f64
            };

            return (max_left + min_right) / 2.0;
        }
    }

    0.0
}

fn main() {
    let nums1 = vec![1, 3];
    let nums2 = vec![2];
    println!("The median is: {}", find_median_sorted_arrays(nums1, nums2));
}

这段 Rust 代码实现了寻找两个有序数组的中位数的算法。它首先确保nums1是较短的数组，然后使用二分查找来找到中位数。在main函数中，给出了两个数组的示例，并调用find_median_sorted_arrays函数来计算并打印中位数。

总结

上述解法采用了二分查找算法来寻找两个有序数组的中位数，以满足时间复杂度为O(log(m+n))的要求。这种方法不需要将两个数组合并，而是通过找到正确的分割点来直接计算中位数。以下是解法的关键步骤：

确保nums1是两个数组中较短的一个，这样可以保证二分查找的范围更小，从而优化性能。
初始化两个指针imin和imax，分别指向nums1的起始位置和结束位置。
计算两个数组的长度之和的一半half_len，这将帮助我们找到中位数的位置。
使用二分查找，通过调整imin和imax来找到正确的分割点。分割点左侧的元素数量等于half_len。
在每次迭代中，计算nums1的分割点i和nums2的分割点j，以保证i + j = half_len。
根据分割点两侧元素的大小关系调整imin和imax的值，直到找到满足以下条件的分割点：
- nums1[i-1] <= nums2[j]且nums2[j-1] <= nums1[i]，这意味着左侧所有元素都小于等于右侧所有元素。
当找到正确的分割点后，中位数可以通过以下方式计算：
- 如果m + n是奇数，则中位数是左侧部分的最大值。
- 如果m + n是偶数，则中位数是左侧部分的最大值和右侧部分的最小值的平均值。
如果nums1的分割点在数组的起始位置或结束位置，需要特别处理边界情况。

这种方法的优势在于它不需要合并数组，而是通过找到正确的分割点来直接计算中位数，从而大大减少了计算时间和空间复杂度。

hot-100

寻找两个正序数组的中位数

题目要求

解题思路

Golang 版本

C++版本

总结