最小数字游戏

难度: Easy

你有一个下标从 0 开始、长度为偶数的整数数组 nums ，同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏，游戏中每一轮 Alice 和 Bob 都会各自执行一次操作。游戏规则如下：

每一轮，Alice 先从 nums 中移除一个最小元素，然后 Bob 执行同样的操作。
接着，Bob 会将移除的元素添加到数组 arr 中，然后 Alice 也执行同样的操作。
游戏持续进行，直到 nums 变为空。

返回结果数组 arr 。

示例 1：

输入：nums = [5,4,2,3]
输出：[3,2,5,4]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 3 。然后 Bob 先将 3 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [3,2] 。
第二轮开始时，nums = [5,4] 。Alice 先移除 4 ，然后 Bob 移除 5 。接着他们都将元素添加到 arr 中，arr 变为 [3,2,5,4] 。

示例 2：

输入：nums = [2,5]
输出：[5,2]
解释：第一轮，Alice 先移除 2 ，然后 Bob 移除 5 。然后 Bob 先将 5 添加到 arr 中，接着 Alice 再将 2 添加到 arr 中。于是 arr = [5,2] 。

提示：

1 <= nums.length <= 100
1 <= nums[i] <= 100
nums.length % 2 == 0

Submission

运行时间: 20 ms

内存: 16.0 MB

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        nums.sort(reverse=True)
        n = len(nums)//2
        result = []
        for _ in range(n):
            n1 = nums.pop()
            n2 = nums.pop()
            result.append(n2)
            result.append(n1)
        return result

Explain

题解首先对输入数组 nums 进行逆序排序，即从大到小排序。这样，每次通过 nums.pop() 取出的将是数组中当前的最小值。由于 Alice 先移除最小元素，随后 Bob 移除次小元素，这两个元素被加入到结果数组 result 中时，Bob 加入的元素应该在 Alice 加入的元素之前。因此，每次迭代中，先从逆序排序的 nums 中 pop 出两个元素（首先是最小的，然后是次小的），然后先将次小的元素（Bob 移除的）加入到 result，再加入最小的元素（Alice 移除的）。整个过程重复进行，直到 nums 为空。

时间复杂度: O(n log n)

空间复杂度: O(n)

# Solution class definition
class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        # 对 nums 数组进行逆序排序
        nums.sort(reverse=True)
        # 获取需要进行的轮数，即 nums 长度的一半
        n = len(nums) // 2
        # 初始化结果数组
        result = []
        # 进行 n 轮操作
        for _ in range(n):
            # 移除并获取当前最小的元素
            n1 = nums.pop()
            # 移除并获取当前次小的元素
            n2 = nums.pop()
            # Bob 先将次小元素添加到 result
            result.append(n2)
            # Alice 将最小元素添加到 result
            result.append(n1)
        # 返回最终的结果数组
        return result

Explore

是的，题解中的逆序排序确实考虑到了pop()操作默认从数组的尾部移除元素的行为。通过将数组逆序排序（从大到小），数组的尾部就变成了最小的元素。因此，每次使用pop()移除尾部元素时，实际上是移除了当前数组中的最小值。这种方法有效地利用了pop()的默认行为，简化了代码逻辑，使得每次操作直接获得最小值，无需额外的操作或计算。

这个问题指出了题解中的一个潜在错误。根据题目的描述，Alice应该是先操作的，然后是Bob。但在题解中的实现中，Bob先添加次小元素，Alice再添加最小元素，这与题目描述的顺序相反。这可能是解题思路或描述中的一个误区，应该调整实现以确保Alice先添加她移除的最小元素，然后Bob添加次小元素，以符合题目的原始意图。

数组的pop()操作在多数编程语言如Python、JavaScript、Java中通常是可用的，但其行为和效率可能略有不同。例如，在Java中，数组没有内置的pop()方法，通常需要使用ArrayList或其他动态数据结构来实现类似的功能。如果在不支持pop()操作的语言中实现这种逻辑，可以使用动态数组或链表，并手动实现移除最后一个元素的功能，或者直接操作索引来模拟pop()操作。

题解中的逻辑假设了数组长度是偶数，因为它每次迭代中都从数组中移除两个元素。如果数组长度是奇数，当前的实现可能会在最后一次迭代时遇到问题，因为最后只剩一个元素而代码尝试移除两个。这种情况需要额外的处理：例如，可以在迭代之前检查数组长度，如果是奇数，则先处理最后一个元素，或者在迭代中加入条件检查确保不会尝试从只含一个元素的数组中再次pop()。