LCR 139. 训练计划 I
2023-10-09 本文已影响0人
红树_
越过一次次失败，却不丧失热情，才是成功的伟大秘诀。
题目
LC每日一题，参考LCR 139. 训练计划 I。
将所有奇数编号训练项目调整至偶数编号训练项目之前。
- 例子
输入：actions = [1,2,3,4,5]
输出：[1,3,5,2,4] 为一个正确答案
解题思路
- 头尾插入：最先想到最简单的做法直接把数字从头尾重新分配到一个新数组。
- 双指针：考虑用双指针遍历交换偶数和奇数，关键是找到左边的偶数和右边的奇数。
- 头插入：优化头插入的空间复杂度，遇到奇数就和前面的下标交换，交换之后下标加一。
头尾插入
class Solution {
fun trainingPlan(actions: IntArray): IntArray {
// 明显可使用新数组头尾插入
val n = actions.size; var ans = IntArray(n)
var head = 0; var tail = n-1
for(i in 0 .. n-1) {
if(actions[i]%2 == 1) ans[head++] = actions[i]
else ans[tail--] = actions[i]
}
return ans
}
}
复杂度分析
- 时间复杂度：
O(n)，一次循环遍历。 - 空间复杂度：
O(n)，使用了新数组。
双指针
class Solution {
fun trainingPlan(actions: IntArray): IntArray {
// 使用双指针 进行交换
val n = actions.size
var i = 0; var j = n-1
while(i < j) {
while(actions[i]%2 == 1 && i < n-1) i++
while(actions[j]%2 == 0 && j > 0) j--
//此时左边是偶数 右边是奇数 直接交换
if(i < j) {
val tmp = actions[j]
actions[j] = actions[i]
actions[i] = tmp
}
}
return actions
}
}
复杂度分析
- 时间复杂度：
O(n)。 - 空间复杂度：
O(1)。
头插入
class Solution {
fun trainingPlan(actions: IntArray): IntArray {
// 找到奇数插入到数组头部
val n = actions.size
var cur = 0
for(i in 0 until n){
if(actions[i]%2 == 1 && i > cur) { // 把该奇数放到头部
val tmp = actions[i]
actions[i] = actions[cur]
actions[cur] = tmp
cur ++
}
}
return actions
}
}
复杂度分析
- 时间复杂度：
O(n)。 - 空间复杂度：
O(1)。
2023.10.10
