🔗 🟢 2974. Minimum Number Game 1185

tags: `Weekly Contest 377` `陣列(Array)` `排序(Sorting)` `模擬(Simulation)` `堆積(Heap)`

題意

給定一個下標從 $0$ 開始且長度為偶數的整數陣列 $nums$ ，以及一個空陣列 $arr$ 。

Alice 和 Bob 決定玩一個遊戲，遊戲規則如下：

每一回合，Alice 先從 $nums$ 中移除一個最小元素，然後 Bob 執行同樣的操作。
接著，Bob 會將移除的元素添加到陣列 $arr$ 中，然後 Alice 也執行同樣的操作。
遊戲持續進行，直到 $nums$ 變為空。

返回結果陣列 $arr$ 。

思路：排序後兩兩交換

由於遊戲規則是每回合都要移除最小的元素，因此我們可以對 $nums$ 進行排序，使得最小的元素位於前面。

接著可以每次取出下標為 $i$ 和 $i+1$ 的元素，由於添加到 $arr$ 中的元素是相反的，因此可以直接交換這兩個元素的位置。

這樣做可以確保 Alice 和 Bob 每回合移除的都是最小的元素，並且交替添加到 $arr$ 中。

複雜度分析

時間複雜度： $\mathcal{O}(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 是 $nums$ $n u m s$ 的長度。
- 排序 $nums$ 的時間複雜度為 $\mathcal{O}(n \log n)$ 。
空間複雜度： $\mathcal{O}(1)$ ，忽略排序所需的額外空間。

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

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

寫在最後

masterpiece, best quality, high quality,extremely detailed CG unity 8k wallpaper, HDR, High Detail,
1girl, solo, long hair, bangs, brown hair, shirt, long sleeves, dress, white shirt, outdoors, day, white dress, blurry, from side, tree, lips, looking up, building, photo background