What is the best approach for solving the Minimum Number Game?

Sorting the array initially and then simulating the turns with alternating picks between Alice and Bob is the best approach. Optionally, use heaps for optimization.

How do I handle the game simulation in the Minimum Number Game?

You simulate the game by alternating between Alice and Bob, where Alice always picks the smallest remaining number and Bob picks the next smallest.

What data structure should I use to optimize the solution for the Minimum Number Game?

Using a heap (priority queue) allows efficient removal of the smallest elements during each turn, reducing the time complexity of picking elements.

How do I ensure the correct order of elements in the result array for the Minimum Number Game?

After sorting the array, append Alice's and Bob's selections to the result array in the order they picked them during the game simulation.

What are the time and space complexities of the Minimum Number Game solution?

The time complexity is O(n log n) for sorting, with additional complexity for heap operations if used. The space complexity depends on the data structure used for simulation, typically O(n).

#2974

Easy

auto_awesome数组·排序

LeetCode 题解工作台

最小数字游戏

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

数组排序堆（优先队列）模拟

题目描述

你有一个下标从 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

lightbulb

解题思路

方法一：模拟 + 优先队列（小根堆）

我们可以将数组 $\textit{nums}$ 中的元素依次放入一个小根堆中，每次从小根堆中取出两个元素 $a$ 和 $b$ ，然后依次将 $b$ 和 $a$ 放入答案数组中，直到小根堆为空。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberGame(self, nums: List[int]) -> List[int]:
        heapify(nums)
        ans = []
        while nums:
            a, b = heappop(nums), heappop(nums)
            ans.append(b)
            ans.append(a)
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ensure the candidate uses sorting as a first step to solve the problem.
question_mark
Look for the candidate's understanding of simulation and alternating turns.
question_mark
Check if the candidate can optimize using heaps or priority queues.

warning

常见陷阱

外企场景

error
Forgetting to sort the array before simulating the game, which leads to incorrect answers.
error
Improper simulation of the turns, such as not appending the elements in the correct order.
error
Not using efficient data structures like heaps, resulting in higher time complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Modify the problem to have Alice and Bob pick elements based on a different rule, such as alternating picks instead of smallest-first.
arrow_right_alt
Change the number of players and adjust the game mechanics accordingly.
arrow_right_alt
Introduce a condition where players can pick from a specific range of numbers rather than from the entire sorted array.

help

常见问题

外企场景

继续练习

#3080 执行操作标记数组中的元素 #2679 矩阵中的和 #2593 标记所有元素后数组的分数