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

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 n1 = herd1.length;
        int n2 = herd2.length;
        int n3 = herd3.length;
        int left = (n1 + n2 + n3 - 1) / 2 + 1;
        int right = (n1 + n2 + n3) / 2 + 1;
        return (findKMinest3(herd1, 0, n1, herd2, 0, n2, herd3, 0, n3, left) +
                findKMinest3(herd1, 0, n1, herd2, 0, n2, herd3, 0, n3, right)) / 2.0;
    }

    private int findKMinest3(int[] herd1, int l1, int r1, int[] herd2, int l2, int r2,
                             int[] herd3, int l3, int r3, int k) {
        int len1 = r1 - l1;
        int len2 = r2 - l2;
        int len3 = r3 - l3;

        if (len2 < len1 && len2 <= len3) {
            return findKMinest3(herd2, l2, r2, herd1, l1, r1, herd3, l3, r3, k);
        }
        if (len3 < len1) {
            return findKMinest3(herd3, l3, r3, herd2, l2, r2, herd1, l1, r1, k);
        }
        if (l1 == r1) {
            return findKMinest(herd2, l2, r2, herd3, l3, r3, k);
        }
        if (k == 1) {
            return Math.min(herd1[l1], Math.min(herd2[l2], herd3[l3]));
        }
        int i = l1 + Math.min(len1, k / 2) - 1;
        int j = l2 + k / 2 - 1;
        int q = l3 + k / 2 - 1;
        int min = Math.min(herd1[i], Math.min(herd2[j], herd3[q]));
        if (min == herd1[i]) {
            return findKMinest3(herd1, i + 1, r1, herd2, l2, r2, herd3, l3, r3, k - (i + 1 - l1));
        } else if (min == herd2[j]) {
            return findKMinest3(herd1, l1, r1, herd2, j + 1, r2, herd3, l3, r3, k - (j + 1 - l2));
        } else {
            return findKMinest3(herd1, l1, r1, herd2, l2, r2, herd3, q + 1, r3, k - (q + 1 - l3));
        }
    }


    // 两个数组
    private static int findKMinest(int[] nums1, int l1, int r1, int[] nums2, int l2, int r2, int k) {
        int len1 = r1 - l1;
        int len2 = r2 - l2;
        // 不管迭代多少次，如果有一个数组被全部排除，一定是第一个
        if (len1 > len2)
            return findKMinest(nums2, l2, r2, nums1, l1, r1, k);
        if (l1 == r1)
            return nums2[l2 + k - 1];

        if (k == 1)
            return Math.min(nums1[l1], nums2[l2]);
        // 找到两个数组的比较位置
        int i = l1 + Math.min(k / 2, len1) - 1;
        int j = l2 + k / 2 - 1;
        if (nums1[i] > nums2[j]) {
            return findKMinest(nums1, l1, r1, nums2, j + 1, r2, k - (j - l2 + 1));
        } else {
            return findKMinest(nums1, i + 1, r1, nums2, l2, r2, k - (i - l1 + 1));
        }
    }
}

同题77，三个数组的分治，并没有什么新的难点，不如上一题