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
}
执行结果：
执行用时： 12 ms , 在所有 Go 提交中击败了 98.74% 的用户 内存消耗： 6.2 MB , 在所有 Go 提交中击败了 91.20% 的用户 通过测试用例： 61 / 61 炫耀一下:
本文由 mdnice 多平台发布