2164-对奇偶下标分别排序

给你一个下标从 0 开始的整数数组 nums 。根据下述规则重排 nums 中的值：

1. 按 非递增 顺序排列 nums 奇数下标 上的所有值。
   * 举个例子，如果排序前 nums = [4, _ **1**_ ,2, _ **3**_ ] ，对奇数下标的值排序后变为 [4, _ **3**_ ,2, _ **1**_ ] 。奇数下标 1 和 3 的值按照非递增顺序重排。
2. 按 非递减 顺序排列 nums 偶数下标 上的所有值。
   * 举个例子，如果排序前 nums = [ _ **4**_ ,1, _ **2**_ ,3] ，对偶数下标的值排序后变为 [ _ **2**_ ,1, _ **4**_ ,3] 。偶数下标 0 和 2 的值按照非递减顺序重排。

返回重排 nums 的值之后形成的数组。

示例 1：

**输入：** nums = [4,1,2,3]
**输出：** [2,3,4,1]
**解释：**
首先，按非递增顺序重排奇数下标（1 和 3）的值。
所以，nums 从 [4, _ **1**_ ,2, _ **3**_ ] 变为 [4, _ **3**_ ,2, _ **1**_ ] 。
然后，按非递减顺序重排偶数下标（0 和 2）的值。
所以，nums 从 [ _ **4**_ ,1, _ **2**_ ,3] 变为 [ _ **2**_ ,3, _ **4**_ ,1] 。
因此，重排之后形成的数组是 [2,3,4,1] 。

示例 2：

**输入：** nums = [2,1]
**输出：** [2,1]
**解释：**
由于只有一个奇数下标和一个偶数下标，所以不会发生重排。
形成的结果数组是 [2,1] ，和初始数组一样。 

提示：

• 1 <= nums.length <= 100
• 1 <= nums[i] <= 100

方法一：按要求操作

思路与算法

我们可以用 even 和 odd 两个辅助数组分别存储数组 nums 的奇偶下标元素，随后对两个数组按要求排序：even 升序排序，odd 降序排序。最终，我们将排序后的 even 和 odd 数组的元素交替放回 nums 中，具体地：

• nums}[2i] = \textit{even}[i]，

• nums}[2i+1] = \textit{odd}[i]

最终，我们返回更新后的 nums 数组作为答案。

代码

[sol1-C++]

class Solution {
public:
    vector<int> sortEvenOdd(vector<int>& nums) {
        vector<int> even, odd;
        for (int i = 0; i < nums.size(); ++i) {
            if (i % 2 == 0) {
                even.push_back(nums[i]);
            }
            else {
                odd.push_back(nums[i]);
            }
        }
        sort(even.begin(), even.end());
        sort(odd.begin(), odd.end(), greater<int>());
        for (int i = 0; i < even.size(); ++i) {
            nums[2*i] = even[i];
        }
        for (int i = 0; i < odd.size(); ++i) {
            nums[2*i+1] = odd[i];
        }
        return nums;
    }
};

[sol1-Python3]

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even = sorted(nums[::2])
        odd = sorted(nums[1::2])[::-1]
        nums[::2] = even
        nums[1::2] = odd
        return nums

复杂度分析

• 时间复杂度：O(n \log n)，其中 n 为 nums 的长度。即为对数组奇偶下标分别排序的时间复杂度。

• 空间复杂度：O(n)，即为辅助数组的空间开销。