【LeetCode】极大极小游戏 Java 题解

2022 年 6 月 11 日
本文字数：1007 字
阅读完需：约 3 分钟

题目描述

给你一个下标从 0 开始的整数数组 nums ，其长度是 2 的幂。

对 nums 执行下述算法：

设 n 等于 nums 的长度，如果 n == 1 ，终止算法过程。否则，创建一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。对于满足 0 <= i < n / 2 的每个偶数下标 i ，将 newNums[i] 赋值为 min(nums[2 * i], nums[2 * i + 1]) 。对于满足 0 <= i < n / 2 的每个奇数下标 i ，将 newNums[i] 赋值为 max(nums[2 * i], nums[2 * i + 1]) 。用 newNums 替换 nums 。从步骤 1 开始重复整个过程。执行算法后，返回 nums 中剩下的那个数字。

示例 1：
输入：nums = [1,3,5,2,4,8,2,2]输出：1解释：重复执行算法会得到下述数组。第一轮：nums = [1,5,4,2]第二轮：nums = [1,4]第三轮：nums = [1]1 是最后剩下的那个数字，返回 1 。
示例 2：
输入：nums = [3]输出：3解释：3 就是最后剩下的数字，返回 3 。
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/min-max-game著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是数组处理题目, 整个题意比较长，自定了一种算法，若当前索引为奇数，求 nums[i] = Math.max(nums[2 * i], nums[2 * i + 1]); 若当前位置是偶数，nums[i] = Math.min(nums[2 * i], nums[2 * i + 1])，直到剩下一个数字就是答案，返回即可。
题目描述定义了 newNums，注意这里不要被他蒙蔽。在实现朴素算法的时候，每次数组长度缩减 n /= 2, 这样的话，我们就不要定义一个新的数组来进行操作。直接在原数组上修改相应的数值即可。实现代码如下，供参考。

通过代码

class Solution {    public int minMaxGame(int[] nums) {        int ans = 0;        int n = nums.length;        if (n == 1) {            ans = nums[0];            return ans;        }        while (n > 1) {            for (int i = 0; i < n / 2; i++) {                if (i % 2 != 0) {                    nums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);                } else {                    nums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);                }            }            n /= 2;        }                ans = nums[0];        return ans;    }}