解题思路

为了找到两个升序数组合并后的下中位数，我们可以使用双指针的方法。具体步骤如下：

  1. 合并两个数组：

    • 使用两个指针分别指向两个数组的起始位置，逐步比较并合并两个数组。

  2. 计算中位数：

    • 由于我们只需要下中位数，可以在合并过程中只记录前半部分的元素。
    • 当合并的元素个数达到 (len1 + len2) / 2 时，返回当前的元素。

  3. 处理偶数情况：

    • 如果合并后的数组长度为偶数，返回中间两个元素中的较小值。

代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int getUpMedian(vector<int>& arr1, vector<int>& arr2) {
        int len1 = arr1.size(), len2 = arr2.size();
        int totalLength = len1 + len2;
        int midIndex = totalLength / 2;
        int i = 0, j = 0, current = 0, last = 0;

        while (i < len1 || j < len2) {
            last = current; // 记录上一个元素
            if (i < len1 && (j >= len2 || arr1[i] <= arr2[j])) {
                current = arr1[i++];
            } else {
                current = arr2[j++];
            }

            // 当合并的元素个数达到中位数位置时返回
            if (i + j - 1 == midIndex) {
                if (totalLength % 2 == 0) {
                    return min(current, last); // 偶数情况，返回较小的
                } else {
                    return current; // 奇数情况，返回当前元素
                }
            }
        }
        return -1; // 这行代码理论上不会被执行
    }
};

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param arr1 int整型一维数组 
     * @param arr2 int整型一维数组 
     * @return int整型
     */
    public int getUpMedian(int[] arr1, int[] arr2) {
        int len1 = arr1.length, len2 = arr2.length;
        int totalLength = len1 + len2;
        int midIndex = totalLength / 2;
        int i = 0, j = 0, current = 0, last = 0;

        while (i < len1 || j < len2) {
            last = current; // 记录上一个元素
            if (i < len1 && (j >= len2 || arr1[i] <= arr2[j])) {
                current = arr1[i++];
            } else {
                current = arr2[j++];
            }

            // 当合并的元素个数达到中位数位置时返回
            if (i + j - 1 == midIndex) {
                if (totalLength % 2 == 0) {
                    return Math.min(current, last); // 偶数情况，返回较小的
                } else {
                    return current; // 奇数情况，返回当前元素
                }
            }
        }
        return -1; // 这行代码理论上不会被执行
    }
}

class Solution:
    def getUpMedian(self, arr1, arr2):
        len1, len2 = len(arr1), len(arr2)
        total_length = len1 + len2
        mid_index = total_length // 2
        i, j = 0, 0
        current, last = 0, 0

        while i < len1 or j < len2:
            last = current  # 记录上一个元素
            if i < len1 and (j >= len2 or arr1[i] <= arr2[j]):
                current = arr1[i]
                i += 1
            else:
                current = arr2[j]
                j += 1

            # 当合并的元素个数达到中位数位置时返回
            if i + j - 1 == mid_index:
                if total_length % 2 == 0:
                    return min(current, last)  # 偶数情况，返回较小的
                else:
                    return current  # 奇数情况，返回当前元素

        return -1  # 这行代码理论上不会被执行

算法及复杂度

  • 算法：双指针
  • 时间复杂度：，其中 和 分别是两个数组的长度
  • 空间复杂度：，只使用了常数级的额外空间