题目:训练计划 I
训练计划 I
教练使用整数数组 actions
记录一系列核心肌群训练项目编号。为增强训练趣味性,需要将所有奇数编号训练项目调整至偶数编号训练项目之前。请将调整后的训练项目编号以数组形式返回。
示例 1:
输入:actions = [1,2,3,4,5] 输出:[1,3,5,2,4] 解释:为正确答案之一提示:
0 <= actions.length <= 50000 0 <= actions[i] <= 10000
注意点
- 本题答案不唯一,只需满足前部分为奇数,后部分为偶数即可
解答
- 思路:利用双指针分别找到偶数元素和奇数元素,执行交换即可,指针碰撞时重组完成
vector<int> trainingPlan(vector<int>& actions) {
int i=0, j=actions.size()-1;
while(i<j){
while(i<j && actions[i]%2) ++i;
while(i<j && !(actions[j]%2)) --j;
swap(actions[i], actions[j]);
}
return actions;
}
- 代码中的细节:
- 为什么 j 从数组尾部开始遍历?因为如果 j 从 0 开始遍历(假设外循环条件是 j 不越界),如果 0 处是奇数,j 无法进入循环,此时 i 跑到 j 的后面去了,会将后面的偶数换到前面的 j 处,违反题目要求
- 为什么正确解答中,在外循环已经对 i<j 做检查的情况下,内循环仍然需要对 i<j 做检查?因为当内循环中 i 一直找不到偶数时,i 可能大于 j,此时会发生如第一点提到的: i 跑到 j 的后面去了,会将后面的偶数换到前面的 j 处