Easy

题目描述

给你一个下标从 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,3,2,1] 变为 [2,3,4,1] 。
因此，重排之后形成的数组是 [2,3,4,1] 。

示例 2：

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

提示：

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

解题思路

这道题要求我们分别对奇数索引和偶数索引的元素进行不同的排序：

  • 奇数索引：非递增排序（降序）
  • 偶数索引：非递减排序（升序）

解题思路：

  1. 分离元素：遍历数组，将奇数索引和偶数索引的元素分别存储到两个列表中
  2. 独立排序：
    • 对偶数索引元素进行升序排序
    • 对奇数索引元素进行降序排序
  3. 重新组合：按照原来的索引位置，将排序后的元素重新填入结果数组

这种方法的优点是思路清晰，代码简洁易懂。我们可以使用两个指针分别追踪偶数和奇数索引排序后元素的位置，然后按原索引顺序重新构建数组。

时间复杂度主要来自排序操作，空间复杂度来自存储分离后的元素。

代码实现

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.rbegin(), odd.rend());  // 降序
        
        // 重新组合
        vector<int> result(nums.size());
        int evenIdx = 0, oddIdx = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i % 2 == 0) {
                result[i] = even[evenIdx++];
            } else {
                result[i] = odd[oddIdx++];
            }
        }
        
        return result;
    }
};

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        even = []
        odd = []
        
        # 分离奇偶索引元素
        for i in range(len(nums)):
            if i % 2 == 0:
                even.append(nums[i])
            else:
                odd.append(nums[i])
        
        # 排序
        even.sort()  # 升序
        odd.sort(reverse=True)  # 降序
        
        # 重新组合
        result = [0] * len(nums)
        even_idx = odd_idx = 0
        for i in range(len(nums)):
            if i % 2 == 0:
                result[i] = even[even_idx]
                even_idx += 1
            else:
                result[i] = odd[odd_idx]
                odd_idx += 1
        
        return result

public class Solution {
    public int[] SortEvenOdd(int[] nums) {
        List<int> even = new List<int>();
        List<int> odd = new List<int>();
        
        // 分离奇偶索引元素
        for (int i = 0; i < nums.Length; i++) {
            if (i % 2 == 0) {
                even.Add(nums[i]);
            } else {
                odd.Add(nums[i]);
            }
        }
        
        // 排序
        even.Sort(); // 升序
        odd.Sort((a, b) => b.CompareTo(a)); // 降序
        
        // 重新组合
        int[] result = new int[nums.Length];
        int evenIdx = 0, oddIdx = 0;
        for (int i = 0; i < nums.Length; i++) {
            if (i % 2 == 0) {
                result[i] = even[evenIdx++];
            } else {
                result[i] = odd[oddIdx++];
            }
        }
        
        return result;
    }
}

var sortEvenOdd = function(nums) {
    let evenIndices = [];
    let oddIndices = [];
    
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            evenIndices.push(nums[i]);
        } else {
            oddIndices.push(nums[i]);
        }
    }
    
    evenIndices.sort((a, b) => a - b);
    oddIndices.sort((a, b) => b - a);
    
    let result = [];
    let evenIdx = 0;
    let oddIdx = 0;
    
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            result[i] = evenIndices[evenIdx++];
        } else {
            result[i] = oddIndices[oddIdx++];
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n log n)
空间复杂度O(n)

说明：

  • 时间复杂度：O(n log n)，其中 n 是数组长度。主要时间消耗在排序操作上
  • 空间复杂度：O(n)，需要额外的数组来存储分离后的奇偶索引元素

相关题目