leetcode 922. 按奇偶排序数组 II-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 922. 按奇偶排序数组 II。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述
解题思路
执行结果

leetcode 922. 按奇偶排序数组 II.

题目描述

按奇偶排序数组 II

给定一个非负整数数组 nums， nums 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是奇数；当 nums[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例 1：

输入：nums = [4,2,5,7] 输出：[4,5,2,7] 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。示例 2：

输入：nums = [2,3] 输出：[2,3]

提示：

2 <= nums.length <= 2 * 104 nums.length 是偶数 nums 中一半是偶数 0 <= nums[i] <= 1000

进阶：可以不使用额外空间解决问题吗？

解题思路

法1

进阶：可以不使用额外空间解决问题

方法1:双指针\

定义两个指针,一个遍历奇数位一个遍历偶数位
分别找出两个不满足奇数对应奇数,偶数对应偶数的条件时,交换两个指针的对应数值,
循环遍历数组,输出结果

这个实现的时间复杂度也是 O(n)，其中 n 是数组的长度。这种方法只需要遍历一次数组，并且没有使用额外的空间，满足了题目的要求。

时间复杂度(O(n))
空间复杂度(O(1))

执行结果

法1

我们使用两个指针 evenIndex 和 oddIndex 分别表示奇数索引和偶数索引。我们通过遍历数组并比较当前元素的奇偶性来进行交换操作，直到两个指针超出数组的范围。

如果 nums[evenIndex] 是偶数，则说明它已经在正确的位置上，我们将 evenIndex 增加 2。

如果 nums[oddIndex] 是奇数，则说明它已经在正确的位置上，我们将 oddIndex 增加 2。

如果 nums[evenIndex] 是奇数，且 nums[oddIndex] 是偶数，说明它们不满足奇数对应奇数、偶数对应偶数的条件，我们将它们交换，并将 evenIndex 和 oddIndex 分别增加 2。

最后，返回经过排序的数组 nums。

func sortArrayByParityII(nums []int) []int {
 n := len(nums)
 evenIndex := 0
 oddIndex := 1

 for evenIndex < n && oddIndex < n {
  if nums[evenIndex]%2 == 0 {
   evenIndex += 2
  } else if nums[oddIndex]%2 != 0 {
   oddIndex += 2
  } else {
   nums[evenIndex], nums[oddIndex] = nums[oddIndex], nums[evenIndex]
   evenIndex += 2
   oddIndex += 2
  }
 }

 return nums
}