LeetCode 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
题目描述
输入一个整数数组，将数组中的奇数移动到数组的前面，偶数移动到数组的后面。要求在移动的过程中保持奇数和偶数的相对顺序不变。
示例 1： 输入：
[1, 2, 3, 4]输出：[1, 3, 2, 4]或者[3, 1, 2, 4]
示例 2： 输入：
[2, 4, 6]输出：[2, 4, 6]
提示：
- 0 <= 数组长度 <= 50000
- -10000 <= 数组元素 <= 10000
思路分析
思路描述
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func exchange(nums []int) []int {
left, right := 0, len(nums)-1
for left < right {
// 找到偶数
for left < right && nums[left]%2 != 0 {
left++
}
// 找到奇数
for left < right && nums[right]%2 == 0 {
right--
}
// 交换偶数和奇数
if left < right {
nums[left], nums[right] = nums[right], nums[left]
}
}
return nums
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
func trainingPlan(nums []int) []int {
left, right := 0, len(nums)-1
for left < right {
// 找到偶数
for left < right && nums[left]%2 != 0 {
left++
}
// 找到奇数
for left < right && nums[right]%2 == 0 {
right--
}
// 交换偶数和奇数
if left < right {
nums[left], nums[right] = nums[right], nums[left]
}
}
return nums
}
- 时间复杂度：O (n)，其中 n 是数组的长度。我们只需遍历数组一次。
- 空间复杂度：O (1)，我们只使用了常数级别的额外空间。
1
write your code here
相似题目
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！