LeetCode每日一题(4. Median of Two Sorted Arrays)

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000

Explanation: merged array = [1,2,3] and median is 2.

Example 2:

Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000

Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

• nums1.length == m
• nums2.length == n
• 0 <= m <= 1000
• 0 <= n <= 1000
• 1 <= m + n <= 2000
• -106 <= nums1[i], nums2[i] <= 106

---

其实就是实现一个快速排序， 只是我们需要根据两个数组各自的中点在对方数组中的位置决定如何进行合并， 具体的方法是找到一个数组的中点，然后二分搜索另一个数组中第一个大于该值的位置， 然后根据位置来决定是如何进行合并

---

impl Solution {
   
    fn binary_split(nums: Vec<i32>, target: i32) -> (Vec<i32>, Vec<i32>) {
   
        let mut l = 0;
        let mut r = nums.len();
        while l < r {
   
            let m = (l + r) / 2;
            if nums[m] < target {
   
                l = m + 1;
                continue;
1
2
3
4
5
6
7
8
9
10
11
12
13