Easy

题目描述

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

对 nums 应用以下算法：

  1. 设 n 等于 nums 的长度，如果 n == 1 ，终止 进程。否则，创建 一个新的整数数组 newNums ，新数组长度为 n / 2 ，下标从 0 开始。
  2. 对于满足 0 <= i < n / 2 的每个 偶数 下标 i ，将 newNums[i] 赋值 为 min(nums[2 * i], nums[2 * i + 1]) 。
  3. 对于满足 0 <= i < n / 2 的每个 奇数 下标 i ，将 newNums[i] 赋值 为 max(nums[2 * i], nums[2 * i + 1]) 。
  4. 用 newNums 替换 nums 。
  5. 从步骤 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 。

提示：

  • 1 <= nums.length <= 1024
  • 1 <= nums[i] <= 10^9
  • nums.length 是 2 的幂

解题思路

这道题要求我们模拟一个递归过程，每轮都将数组长度缩减一半，直到只剩一个元素。

核心思路：

  1. 直接模拟：按照题目要求逐步执行算法，每轮创建新数组，根据索引奇偶性选择min或max操作
  2. 原地操作优化：可以在原数组上直接修改，避免创建新数组，节省空间

算法流程：

  • 当数组长度大于1时，进入循环
  • 遍历当前数组的前半部分（新数组的位置）
  • 对于新数组的偶数索引位置：取对应两个元素的最小值
  • 对于新数组的奇数索引位置：取对应两个元素的最大值
  • 更新数组长度为原来的一半
  • 重复直到只剩一个元素

复杂度特点： 由于每轮数组长度都减半，总共只需要O(log n)轮，每轮处理O(n)个元素，但由于n在递减，总时间复杂度仍为O(n)。

这是一个典型的模拟题，关键是理解题意并正确实现算法逻辑。

代码实现

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

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        n = len(nums)
        
        while n > 1:
            for i in range(n // 2):
                if i % 2 == 0:
                    nums[i] = min(nums[2 * i], nums[2 * i + 1])
                else:
                    nums[i] = max(nums[2 * i], nums[2 * i + 1])
            n //= 2
        
        return nums[0]

public class Solution {
    public int MinMaxGame(int[] nums) {
        int n = nums.Length;
        
        while (n > 1) {
            for (int i = 0; i < n / 2; i++) {
                if (i % 2 == 0) {
                    nums[i] = Math.Min(nums[2 * i], nums[2 * i + 1]);
                } else {
                    nums[i] = Math.Max(nums[2 * i], nums[2 * i + 1]);
                }
            }
            n /= 2;
        }
        
        return nums[0];
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minMaxGame = function(nums) {
    while (nums.length > 1) {
        let newNums = [];
        for (let i = 0; i < nums.length / 2; i++) {
            if (i % 2 === 0) {
                newNums[i] = Math.min(nums[2 * i], nums[2 * i + 1]);
            } else {
                newNums[i] = Math.max(nums[2 * i], nums[2 * i + 1]);
            }
        }
        nums = newNums;
    }
    return nums[0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)虽然有log n轮，但每轮处理的元素数量递减，总计算量为n + n/2 + n/4 + … ≈ 2n
空间复杂度O(1)原地修改数组，不需要额外空间

相关题目