2164. Sort Even and Odd Indices Independently

方法一：排序 + 按序插入

遍历 nums数组，用 even 和 odd 数组分别存储奇数和偶数，按照题目要求分别 降序和升序处理；

遍历偶数数组 even，每遇到奇数下标，则在奇数下标中插入奇数数组 odd 中的每一个元素；若 nums数组为偶数，最后一个偶数位序未用于插值，因此在 even 数组末尾补上奇数数组 odd 中最后一个元素

Python版本

C++版本

复杂度分析

• 时间复杂度：O(N)。此处的 n 指的是数组 nums的长度。遍历 nums 数组需要 O(N)的复杂度，遍历奇数数组需要 O(N / 2)的复杂度，两者合计为总复杂度，但去掉系数。

• 空间复杂度：O(N)。 此处的 n 指的是数组 nums 的长度，存储奇偶位序的数组空间总和为 O(N)；

方法二：原地修改【映射】

遍历 nums数组分别用数组odd 和数组 even 存储奇数位序，偶数位序对应的元素；遍历奇数数组 odd，按照题目分别降序和升序处理；

我们可以由奇数数组的每一个位序 i， 计算出 nums原数组中奇数位序和偶数位序分别为 2 * i + 1 和 2 * i，按照位序修改值即可。可能存在数组长度为偶数，even 数组长度比 odd 数组的长度大1 的情况，因此修改原数组末尾元素为 even 数组最后一个元素即可；

Python版本

C++版本

复杂度分析

• 时间复杂度： O(N)。 此处 n 为 数组 nums长度，遍历  nums 数组分别存储奇偶数， 遍历奇数数组需要 n / 2 或者 n / 2 + 1 的复杂度，总复杂度为 n / 2 * 3。

• 空间复杂度： O(N)。此处 n 为 数组 nums长度，奇偶分别存储，耗费大小为 n 的额外空间；