题解 | #三个牛群中位数#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的是在三个有序数组中找到合并后的中位数，要求时间复杂度为 O(log (m+n+p))。

题目解答方法的文字分析

给定三个有序数组 herd1、herd2 和 herd3，分别表示三个牛群的牛的体重，并且每个数组都按照体重从小到大的顺序进行排序。

我们的任务是找出这三个正序数组合并后的中位数。

为了实现时间复杂度为 O(log (m+n+p)) 的算法解决此问题，我们可以使用类似于归并排序的思想，同时维护三个指针。

具体步骤如下：

1. 对于合并后的有序数组，如果 m+n+p 是奇数，我们只需要找到第 (m+n+p)/2+1 个元素即可；如果 m+n+p 是偶数，我们需要找到第 (m+n+p)/2 和 (m+n+p)/2+1 个元素，然后求平均值。
2. 我们需要维护三个指针 i、j 和 k 分别指向三个数组 herd1、herd2 和 herd3 的当前元素。
3. 在每次迭代中，我们比较三个指针指向的元素，找到当前三个数组中最小的元素，将其加入合并后的数组，并将对应指针向后移动一位。
4. 当合并后的数组长度达到 (m+n+p)/2+1 时，我们找到了中位数。

本题解析所用的编程语言 (C++)

本题解析所用的编程语言是 C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param herd1 int整型vector 
     * @param herd2 int整型vector 
     * @param herd3 int整型vector 
     * @return double浮点型
     */
    double findMedianSortedArray(vector<int>& herd1, vector<int>& herd2, vector<int>& herd3) {
        int m = herd1.size();
        int n = herd2.size();
        int p = herd3.size();

        int i = 0, j = 0, k = 0;
        vector<int> merged;

        // 合并三个有序数组
        while (i < m && j < n && k < p) {
            if (herd1[i] <= herd2[j] && herd1[i] <= herd3[k]) {
                merged.push_back(herd1[i]);
                i++;
            } else if (herd2[j] <= herd1[i] && herd2[j] <= herd3[k]) {
                merged.push_back(herd2[j]);
                j++;
            } else {
                merged.push_back(herd3[k]);
                k++;
            }
        }

        // 将剩余的元素添加到合并后的数组
        while (i < m) {
            merged.push_back(herd1[i]);
            i++;
        }
        while (j < n) {
            merged.push_back(herd2[j]);
            j++;
        }
        while (k < p) {
            merged.push_back(herd3[k]);
            k++;
        }

        int total = m + n + p;
        if (total % 2 == 0) {
            // 如果数组长度是偶数，返回中位数
            return (merged[total / 2 - 1] + merged[total / 2]) / 2.0;
        } else {
            // 如果数组长度是奇数，直接返回中位数
            return merged[total / 2];
        }
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！