2164. 对奇偶下标分别排序

🟢   🔖  数组 排序  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array nums. Rearrange the values of nums according to the following rules:

1. Sort the values at odd indices of nums in non-increasing order.

• For example, if nums = [4,1 ,2,3] before this step, it becomes [4,3 ,2,1] after. The values at odd indices 1 and 3 are sorted in non-increasing order.

2. Sort the values at even indices of nums in non-decreasing order.

• For example, if nums = [4 ,1,2 ,3] before this step, it becomes [2 ,1,4 ,3] after. The values at even indices 0 and 2 are sorted in non-decreasing order.

Return the array formed after rearranging the values of nums.

Example 1:

Input: nums = [4,1,2,3]

Output: [2,3,4,1]

Explanation:

First, we sort the values present at odd indices (1 and 3) in non-increasing order.

So, nums changes from [4,1 ,2,3] to [4,3 ,2,1].

Next, we sort the values present at even indices (0 and 2) in non-decreasing order.

So, nums changes from [4 ,1,2 ,3] to [2 ,3,4 ,1].

Thus, the array formed after rearranging the values is [2,3,4,1].

Example 2:

Input: nums = [2,1]

Output: [2,1]

Explanation:

Since there is exactly one odd index and one even index, no rearrangement of values takes place.

The resultant array formed is [2,1], which is the same as the initial array.

Constraints:

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

题目大意

给你一个下标从 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

解题思路

1. 分离奇数索引和偶数索引：

   • 遍历数组，分别将偶数索引位置的数字放入数组 even，奇数索引位置的数字放入数组 odd。

2. 排序：

   • 对 even 数组进行升序排序。
   • 对 odd 数组进行降序排序。

3. 重新合并：

   • 遍历原数组，根据索引的奇偶性，将排序后的数字重新放回原数组。

复杂度分析

• 时间复杂度：O(n log n)

  • 遍历数组将数字分为 even 和 odd：O(n)。
  • 对 even 数组升序排序：O((n/2) log(n/2))。
  • 对 odd 数组降序排序：O((n/2) log(n/2))。
  • 合并排序后的数组：O(n)。

  综合时间复杂度为 O(n log n)。

• 空间复杂度：O(n)，需要额外的空间存储 even 和 odd 数组。

代码

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortEvenOdd = function (nums) {
	let even = [];
	let odd = [];

	// 分离奇数索引和偶数索引的数字
	nums.forEach((num, i) => {
		if (i % 2 === 0) {
			even.push(num);
		} else {
			odd.push(num);
		}
	});

	// 对偶数索引部分升序排序
	even.sort((a, b) => a - b);
	// 对奇数索引部分降序排序
	odd.sort((a, b) => b - a);

	// 合并回原数组
	for (let i = 0; i < nums.length; i++) {
		if (i % 2 === 0) {
			nums[i] = even[i / 2];
		} else {
			nums[i] = odd[(i - 1) / 2];
		}
	}
	return nums;
};

相关题目

题号	标题	题解	标签	难度	力扣
905	按奇偶排序数组	[✓]	数组 双指针 排序	🟢	🀄️ 🔗
922	按奇偶排序数组 II	[✓]	数组 双指针 排序	🟢	🀄️ 🔗