极大极小游戏

标签: 数组 模拟

难度: 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] <= 109
  • nums.length 是 2 的幂

Submission

运行时间: 24 ms

内存: 16.1 MB

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:

        def newnums(nums):
            newnums = []
            k = -1
            for i in range(0,len(nums),2):
                if k ==-1:
                    newnums.append(min(nums[i:i+2]))
                else:
                    newnums.append(max(nums[i:i+2]))
                k *= -1
            return newnums
        
        while len(nums)>1:
            nums = newnums(nums)
        return nums[0]

Explain

此题解使用了递归减少的方法来模拟题目描述的算法。在每一轮，函数`newnums`将输入数组`nums`转换成新的数组`newNums`。转换过程中，偶数下标处的元素取两个元素的最小值，奇数下标处的元素取两个元素的最大值。每次迭代后，数组的长度减半，直到数组长度变为1，此时数组中的唯一元素就是结果。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def minMaxGame(self, nums: List[int]) -> int:
        
        def newnums(nums):
            newnums = []  # 创建新数组用于存储每轮的结果
            k = -1  # 用于交替选择最小值和最大值
            for i in range(0, len(nums), 2):
                if k == -1:
                    newnums.append(min(nums[i:i+2]))  # 选择最小值
                else:
                    newnums.append(max(nums[i:i+2]))  # 选择最大值
                k *= -1  # 交替标志
            return newnums  # 返回新生成的数组
        
        while len(nums) > 1:
            nums = newnums(nums)  # 更新nums为新生成的数组
        return nums[0]  # 当数组长度为1时，返回数组中的唯一元素

Explore

算法在数组长度为1时终止，因为这是算法的终止条件——找到最终结果。数组长度变为1意味着经过了一系列的计算后，只剩下一个元素，这个元素即为游戏的结果。如果数组长度为0，这通常表示输入不合法或异常，因为按照题目的设定，至少应有一个元素以进行比较和计算。因此，终止条件设为数组长度为1是为了保证能正常得到游戏的结果，而不是处理空数组的异常情况。

在函数`newnums`中，变量`k`的初始值设为`-1`并通过乘以`-1`来切换，是为了控制选择最小值或最大值的逻辑。初始值为`-1`，第一次计算时`k`的值变为1（`-1 * -1 = 1`），按照代码逻辑，此时选择的是最小值。在下一次迭代时，`k`又变为-1，选择最大值。这种交替方式简单有效地控制了选择逻辑，使代码更为简洁和直观。

递归的深度取决于数组`nums`的长度。因为每次递归调用都会将数组长度减半，所以递归的深度大约是`log2(n)`，其中`n`是数组的初始长度。对于典型的现代计算机和合理的输入大小，这样的递归深度通常不会导致性能问题或栈溢出。然而，对于非常大的输入，任何递归实现都可能面临性能瓶颈或栈溢出的风险，这时可能需要考虑使用迭代方法来优化。

递归方法的优势在于其清晰和直接，代码通常更易于编写和理解。递归方法自然地映射了问题的结构，使得代码更加直观。然而，递归的劣势包括可能的性能问题（如递归调用的开销）和栈溢出风险，特别是对于大规模的数据输入。相比之下，迭代方法通常更为高效，因为它们直接在堆栈上操作，没有额外的函数调用开销，适用于处理大规模数据。但迭代代码可能不如递归直观，需要更多控制结构来管理状态。