我要评论【letmefly】2974.最小数字游戏：排序+交换奇偶位
力扣题目链接：https://leetcode.cn/problems/minimum-number-game/
你有一个下标从 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 <= 1001 <= nums[i] <= 100nums.length % 2 == 0
解题方法：排序
相当于是每次挑选两个最小的数，然后让第二小的数放到第一小的数的前面。
例如[1, 2, 3, 4]会变成[2, 1, 4, 3]。
因此对nums排序，之后用i每隔一个下标遍历数组，交换 n u m s [ i ] nums[i] nums[i]和 n u m s [ i + 1 ] nums[i+1] nums[i+1]，最终返回nums即可。
- 时间复杂度 o ( n log n ) o(n\log n) o(nlogn)，其中 n = l e n ( n u m s ) n=len(nums) n=len(nums)
- 空间复杂度 o ( log n ) o(\log n) o(logn)
ac代码
c++
class solution {
public:
vector<int> numbergame(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0; i + 1 < nums.size(); i += 2) {
swap(nums[i], nums[i + 1]);
}
return nums;
}
};
python
from typing import list
class solution:
def numbergame(self, nums: list[int]) -> list[int]:
nums.sort()
for i in range(0, len(nums) - 1, 2):
nums[i], nums[i + 1] = nums[i + 1], nums[i]
return nums
发表评论