leetcode 922. 按奇偶排序数组 II

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

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

题目描述

922. 按奇偶排序数组 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:双指针\

1. 定义两个指针,一个遍历奇数位一个遍历偶数位

2. 分别找出两个不满足奇数对应奇数,偶数对应偶数的条件时,交换两个指针的对应数值,

3. 循环遍历数组,输出结果

这个实现的时间复杂度也是 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
}

执行结果：

执行用时： 12 ms , 在所有 Go 提交中击败了 98.74% 的用户 内存消耗： 6.2 MB , 在所有 Go 提交中击败了 91.20% 的用户 通过测试用例： 61 / 61 炫耀一下:

本文由 mdnice 多平台发布