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

考察知识点：二分

题目分析：

这道题是上一题的升级版，但是思想是一样的。都是通过二分来达到O(log(m + n + p))的时间复杂度。

由于两个序列都是有序的，找中位数就是找到中间的第k个数。

首先我们假设herd1的长度最小，不满足这个条件的就将函数参数调换一下顺序。如果herd1的长度是0，那么就只需要找到两个序列中的中位数，用上一题解法即可。

为了能找到第k个数，我们设法每一次排除k / 2个数。可以分别在数组herd1、herd2和herd3中找到第k / 2个数。

找到这三个数中最小的那一个，它前面的数一定不是我们要找的结果，所以可以直接排除herd2中的10、20、30。排除完以后，k只需要在剩余序列中找第k - 3个数，将herd2的起始索引更新，递归计算即可。注意递归时总是保证herd1是最短的序列，原来的herd1会和其他序列相互交换。

所用编程语言：C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param herd1 int整型vector 
     * @param herd2 int整型vector 
     * @param herd3 int整型vector 
     * @return double浮点型
     */
    int getKth(vector<int> &herd1, int l1, int r1, vector<int> &herd2, int l2, int r2, int k) {
        int len1 = r1 - l1 + 1;
        int len2 = r2 - l2 + 1;
        if (len1 > len2) 
            return getKth(herd2, l2, r2, herd1, l1, r1, k);
        if (len1 == 0) 
            return herd2[l2 + k - 1];
        if (k == 1) 
            return min(herd1[l1], herd2[l2]);
        
        int i = l1 + min(len1, k / 2) - 1;
        int j = l2 + k / 2 - 1;
        if (herd1[i] <= herd2[j])
            return getKth(herd1, i + 1, r1, herd2, l2, r2, k - (i - l1 + 1));
        else 
            return getKth(herd1, l1, r1, herd2, j + 1, r2, k - (j - l2 + 1));
    }
    int getKth_3(vector<int> &herd1, int l1, int r1, vector<int> &herd2, int l2, int r2, vector<int> &herd3, int l3, int r3, int k) {
        int len1 = r1 - l1 + 1;
        int len2 = r2 - l2 + 1;
        int len3 = r3 - l3 + 1;

        if (len2 < len1 && len2 <= len3) 
            return getKth_3(herd2, l2, r2, herd1, l1, r1, herd3, l3, r3, k);
        if (len3 < len1)
            return getKth_3(herd3, l3, r3, herd2, l2, r2, herd1, l1, r1, k);

        if (len1 == 0) 
            return getKth(herd2, l2, r2, herd3, l3, r3, k);

        if (k == 1) 
            return min(herd1[l1], min(herd2[l2], herd3[l3]));

        int u = l1 + min(len1, k / 2) - 1;
        int v = l2 + k / 2 - 1;
        int w = l3 + k / 2 - 1;
        int min_val = min(herd1[u], min(herd2[v], herd3[w]));
        if (min_val == herd1[u]) 
            return getKth_3(herd1, u + 1, r1, herd2, l2, r2, herd3, l3, r3, k - (u - l1 + 1));
        else if (min_val == herd2[v]) 
            return getKth_3(herd1, l1, r1, herd2, v + 1, r2, herd3, l3, r3, k - (v - l2 + 1));
        else
            return getKth_3(herd1, l1, r1, herd2, l2, r2, herd3, w + 1, r3, k - (w - l3 + 1));
    }
    double findMedianSortedArray(vector<int>& herd1, vector<int>& herd2, vector<int>& herd3) {
        // write code here
        int size1 = herd1.size();
        int size2 = herd2.size();
        int size3 = herd3.size();
        int size = size1 + size2 + size3;
        int left = (size + 1) / 2;
        int right = (size + 2) / 2;
        return (getKth_3(herd1, 0, size1 - 1, herd2, 0, size2 - 1, herd3, 0, size3 - 1, left) + getKth_3(herd1, 0, size1 - 1, herd2, 0, size2 - 1, herd3, 0, size3 - 1, right)) * 0.5;
    }
};