LCR 139. 训练计划 I

越过一次次失败，却不丧失热情，才是成功的伟大秘诀。

题目

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