Easy

题目描述

给你一个长度为偶数的整数数组 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 先添加，Alice 后添加。所以 arr = [5,2]。

提示：

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

解题思路

这道题的核心是理解游戏规则和找到简化的解决方案。

思路分析：

  1. 模拟过程：按照题意，每轮游戏都是先移除两个最小元素，然后按照 Bob 先、Alice 后的顺序添加到结果数组。

  2. 关键洞察：由于每次都是取最小元素，我们可以先对数组排序。排序后，每相邻的两个元素就是每轮游戏中 Alice 和 Bob 分别取到的元素。

  3. 简化操作：

    • Alice 取到的是较小的元素（索引为偶数位置）
    • Bob 取到的是较大的元素（索引为奇数位置）
    • 由于 Bob 先添加到结果数组，所以结果中应该是 Bob 的元素在前，Alice 的元素在后

  4. 具体实现：对排序后的数组，每两个相邻元素交换位置即可得到最终结果。

这种方法避免了复杂的模拟过程，时间复杂度主要由排序决定。

推荐解法：排序 + 相邻元素交换，这是最优解法。

代码实现

class Solution {
public:
    vector<int> numberGame(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i += 2) {
            swap(nums[i], nums[i + 1]);
        }
        
        return nums;
    }
};

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        nums.sort()
        
        for i in range(0, len(nums), 2):
            nums[i], nums[i + 1] = nums[i + 1], nums[i]
        
        return nums

public class Solution {
    public int[] NumberGame(int[] nums) {
        Array.Sort(nums);
        
        for (int i = 0; i < nums.Length; i += 2) {
            int temp = nums[i];
            nums[i] = nums[i + 1];
            nums[i + 1] = temp;
        }
        
        return nums;
    }
}

var numberGame = function(nums) {
    nums.sort((a, b) => a - b);
    
    for (let i = 0; i < nums.length; i += 2) {
        [nums[i], nums[i + 1]] = [nums[i + 1], nums[i]];
    }
    
    return nums;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n log n)主要由排序算法决定
空间复杂度O(1)原地修改数组，不使用额外空间