LeetCodeHOT100：60. n个骰子的点数、4. 寻找两个正序数组的中位数

LeetCodeHOT100：

剑指 Offer 60. n个骰子的点数
4. 寻找两个正序数组的中位数
96. 不同的二叉搜索树

剑指 Offer 60. n个骰子的点数

题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
示例 1：
输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

思路分析： 时间复杂度为 $O(n^3)$ ，其中第一个循环的次数是 $n$ ，第二个循环的次数是 $6 n$ ，第三个循环的次数是 $6$ ，因此总次数为 $\times 6n \times 6 = O(n^3)$ 。

空间复杂度为 $O(n^2)$ ，需要开辟一个二维数组 dp，大小为 $\times (6n+1)$ 。

class Solution {
    public double[] dicesProbability(int n) {
        // 特判，当 n 为 0 时，返回空数组
        if (n == 0) {
            return new double[0];
        }

        // 创建一个二维数组 dp，dp[i][j] 表示投掷 i 个骰子，点数之和为 j 的次数
        int[][] dp = new int[n + 1][6 * n + 1];

        // 初始化只投掷一个骰子的情况，即 dp[1][1~6] = 1
        for (int i = 1; i <= 6; i++) {
            dp[1][i] = 1;
        }

        // 从投掷两个骰子开始，逐渐增加骰子个数
        for (int i = 2; i <= n; i++) {
            // 对于每个骰子数之和 j，枚举最后一个骰子的点数 k
            for (int j = i; j <= 6 * n; j++) {
                for (int k = 1; k <= 6; k++) {
                    // 如果 j 大于等于 k，则 j-k 是一个合法的下标
                    if (j >= k) {
                        // 计算投掷 i 个骰子，点数之和为 j 的次数
                        dp[i][j] += dp[i - 1][j - k];
                    }
                }
            }
        }

        // 计算所有情况的可能性总数，即 6 的 n 次方
        double count = Math.pow(6, n);

        // 创建一个长度为 5*n+1 的数组 res，用于存储所有可能点数的概率
        double[] res = new double[5 * n + 1];
        int index = 0;
        // 枚举所有可能点数 i，将 dp[n][i] 除以总次数 count 得到概率
        for (int i = n; i <= 6 * n; i++) {
            res[index++] = dp[n][i] / count;
        }

        return res;
    }
}

4. 寻找两个正序数组的中位数

题目：给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

思路分析： 假设我们要找出两个数组中的第k小的数，我们可以比较两个数组的中位数mid1和mid2，假设mid1小于mid2，则nums1中前k/2个元素一定不可能是第k小的数（因为nums1中前k/2个元素加上nums2中前k/2个元素最多只能组成k个元素，而这k个元素中已经有mid1和mid2了，因此nums1中前k/2个元素一定不可能是第k小的数），因此我们可以将这些元素删除。此时，我们需要在nums1的剩余元素和nums2中查找第k-k/2小的数，这可以通过递归实现。为了避免每次都将数组的前k/2个元素都复制到一个新的数组中，我们可以使用指针来标记当前查找的区域，在每次递归调用时调整指针即可。具体来说，我们可以编写一个名为findK的函数，该函数接收四个参数：数组nums1、数组nums2、两个指针l1和l2，以及要查找的第k小的数。函数的返回值是两个数组中第k小的数。在每次递归调用中，我们需要判断各种边界条件，以避免出现数组下标越界等错误。其中，如果k=1，则说明我们已经找到了当前查找的中位数，此时只需要返回两个数组中较小的那个元素即可。如果删除这个条件，则在递归查找的过程中无法正确判断何时已经找到了中位数，从而导致错误的结果。在计算中位数时，我们需要分别处理数组长度为奇数和偶数的情况。如果数组长度为奇数，则中位数是第(len+1)/2个元素；如果数组长度为偶数，则中位数是第len/2个元素和第(len+2)/2个元素的平均值。最后，我们可以编写一个名为findMedianSortedArrays的函数，该函数接收两个已排序的数组nums1和nums2，并返回它们的中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 计算两个数组的总长度
        int len = nums1.length + nums2.length;
        // 如果总长度为奇数，则中位数是第(len+1)/2个数
        if (len % 2 == 1) {
            return findK(nums1, 0, nums2, 0, (len + 1) / 2) * 1.0;
        } else { // 如果总长度为偶数，则中位数是第len/2个数和第(len+2)/2个数的平均值
            return (findK(nums1, 0, nums2, 0, len / 2) + findK(nums1, 0, nums2, 0, (len + 2) / 2)) * 0.5;
        }
    }

    // 在两个数组中查找第k小的数
    private int findK(int[] nums1, int l1, int[] nums2, int l2, int k) {
        // 如果nums1中已经没有元素，则第k小的数在nums2中
        if (l1 >= nums1.length) {
            return nums2[l2 + k - 1];
        }

        // 如果nums2中已经没有元素，则第k小的数在nums1中
        if (l2 >= nums2.length) {
            return nums1[l1 + k - 1];
        }

        // 如果k=1，则第k小的数就是nums1和nums2中较小的那个
        if (k == 1) {
            return Math.min(nums1[l1], nums2[l2]);
        }

        // 在nums1和nums2中各取k/2个元素进行比较
        int mid1 = Integer.MAX_VALUE;
        int mid2 = Integer.MAX_VALUE;
        if (nums1.length - l1 >= k / 2) {
            mid1 = nums1[l1 + k / 2 - 1];
        }

        if (nums2.length - l2 >= k / 2) {
            mid2 = nums2[l2 + k / 2 - 1];
        }

        // 如果nums1中的中位数小于nums2中的中位数，则第k小的数一定不在nums1的前k/2个元素中，可以排除这些元素，继续在剩余的元素中查找第k-k/2小的数；否则第k小的数一定不在nums2的前k/2个元素中，可以排除这些元素，继续在剩余的元素中查找第k-k/2小的数
        if (mid1 < mid2) {
            return findK(nums1, l1 + k / 2, nums2, l2, k - k / 2);
        } else {
            return findK(nums1, l1, nums2, l2 + k / 2, k - k / 2);
        }
    }
}