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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param herd1 int整型一维数组
     * @param herd2 int整型一维数组
     * @param herd3 int整型一维数组
     * @return double浮点型
     */
    public double findMedianSortedArray (int[] herd1, int[] herd2, int[] herd3) {
        // write code here
      int h1 = herd1.length;
        int h2 = herd2.length;
        int h3 = herd3.length;
        int[] nums1 = new int[h1 + h2 + h3];
        for (int i = 0; i < h1; i++) {
            nums1[i] = herd1[i];
        }
        for (int i = 0; i < h2; i++) {
            nums1[h1 + i] = herd2[i];
        }
        for (int i = 0; i < h3; i++) {
            nums1[h1 + h2 + i] = herd3[i];
        }
        Arrays.sort(nums1);
        int n = nums1.length;
        if (n % 2 == 0) {
            return (nums1[n / 2] + nums1[n / 2 - 1]) / 2.0;
        } else {
            return nums1[n / 2];
        }
    }
}

考察的知识点：

1. 分治和二分查找：通过分治思想将问题分解为在三个有序数组中找第 k 小的元素，然后利用二分查找的方法进行查找。
2. 数组操作：在有序数组中查找元素并更新指针。
3. 数学处理：根据奇偶情况返回中位数。

解题思路：

类似于之前讨论的问题，我们可以使用分治和二分查找的思想来解决这个问题。假设我们要找的是第 (m + n + p) / 2 小的元素，我们可以将问题分解为在三个有序数组中分别找第 k 小的元素。

我们可以首先分别找出第 k/3 小的元素在三个数组中的位置，然后比较这三个位置上的元素，选取其中最小的一个。接着，根据最小元素所在的数组，更新数组的起始位置，以及 k 的值。每次递归缩小问题规模，直到 k 缩小到 1，此时我们找到了中位数。