对奇偶下标分别排序

标签: 数组 排序

难度: 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,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

Submission

运行时间: 25 ms

内存: 16.1 MB

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

Explain

题解首先通过分割原数组 nums，将奇数下标和偶数下标的元素分别收集。使用 Python 列表切片操作，nums[::2] 获取所有偶数下标的元素，nums[1::2] 获取所有奇数下标的元素。随后对偶数下标的元素进行非递减排序，对奇数下标的元素进行非递增排序。非递增排序是通过先对元素进行非递减排序后再反转列表实现的。最后，将排序后的元素按原下标重新赋值给 nums，并返回修改后的 nums。

时间复杂度: O(n log n)

空间复杂度: O(n)

class Solution:
    def sortEvenOdd(self, nums: List[int]) -> List[int]:
        # 对偶数下标的元素进行非递减排序
        nums[::2] = sorted(nums[::2])
        # 对奇数下标的元素进行非递增排序（先排序，后反转）
        nums[1::2] = sorted(nums[1::2])[::-1]
        # 返回重排后的数组
        return nums

Explore

在 Python 中，使用切片操作如 nums[::2] 和 nums[1::2] 实际上是创建了原数组的副本，而不是直接操作原数组。这意味着当我们对 nums[::2] 进行排序时，我们实际上是在对其副本进行操作，排序完毕后再将排序后的副本赋值回原数组的相应位置。这个过程确保了对一个切片的修改不会影响到另一个切片。因此，先对偶数下标的元素进行排序并不会影响奇数下标元素的初始状态，反之亦然。

虽然在某些编程语言中，排序函数提供了直接按降序排序的选项（例如 Python 的 sorted 函数可以通过设置参数 reverse=True 实现降序排序），但选择先按非递减排序再反转列表的做法可以更加直观地展示排序和反转的逻辑关系，并且保持代码的一致性和可读性。此外，对于初学者来说，这种方法能更清晰地理解排序后的数据结构变化。

此算法也适用于数组长度非常小的情况。如果数组只有一个元素，该元素既被视为偶数下标也是奇数下标的唯一元素，但由于排序和反转操作都不会改变单个元素的位置或值，所以算法仍然有效。如果数组有两个元素，第一个元素为偶数下标，第二个元素为奇数下标，它们各自被排序后仍会保持在原来的位置。因此，不需要特别的边界处理措施，算法在这些情况下都能正确执行。

理论上，由于偶数下标和奇数下标的元素排序是互不影响的，这两个操作可以通过并行执行来提高效率。在多线程或多进程的编程环境中，可以将偶数下标元素的排序和奇数下标元素的排序分配到不同的线程或进程中执行。然而，这种优化是否值得实施取决于原数组的大小以及系统对并行计算的支持。对于较小的数组，由于线程创建和管理的开销，这种优化可能不会带来显著的性能提升。