rp做网站,郑州小程序设计外包,wordpress如何导入主题,如果快速做网站【LetMeFly】2974.最小数字游戏#xff1a;排序交换奇偶位
力扣题目链接#xff1a;https://leetcode.cn/problems/minimum-number-game/
你有一个下标从 0 开始、长度为 偶数 的整数数组 nums #xff0c;同时还有一个空数组 arr 。Alice 和 Bob 决定玩一个游戏#xff…【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[i1] nums[i1]最终返回nums即可。
时间复杂度 O ( n log n ) O(n\log n) O(nlogn)其中 n l e n ( n u m s ) nlen(nums) nlen(nums)空间复杂度 O ( log n ) O(\log n) O(logn)
AC代码
C
class Solution {
public:vectorint numberGame(vectorint 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 Listclass 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同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/140365205
