題目

教練使用整數數組 actions 記錄一系列核心肌群訓練項目編號。為增強訓練趣味性，需要將所有奇數編號訓練項目調整至偶數編號訓練項目之前。請將調整后的訓練項目編號以 數組 形式返回。

示例 1：

輸入：actions = [1,2,3,4,5]
輸出：[1,3,5,2,4]
解釋：為正確答案之一

提示：

0 <= actions.length <= 50000
0 <= actions[i] <= 10000

---

題解

本題目考慮定義雙指針解決。指針 i,j 分列數組左右兩端，循環執行：

• 指針i從左向右尋找偶數；
• 指針j從右向左尋找奇數；
• 將偶數actions[i]和 奇數actions[j]交換。

這樣可始終保證： 指針 i 左邊都是奇數，指針 j 右邊都是偶數 。

通過對2取余可判斷是不是奇數，此處可以使用位運算來快速取余 actions[i] & 1。

class Solution(object):def trainingPlan(self, actions):""":type actions: List[int]:rtype: List[int]"""i,j = 0, len(actions) - 1while i < j:while i < j and actions[i] % 2 == 1: i += 1while i < j and actions[j] % 2 == 0: j -= 1actions[i], actions[j] = actions[j], actions[i]return actions

• 時間復雜度O(N)： N為數組actions長度，雙指針i,j共同遍歷整個數組。
• 空間復雜度O(1)：雙指針i,j使用常數大小的額外空間。

Reference

1. https://leetcode.cn/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/solutions/115087/mian-shi-ti-21-diao-zheng-shu-zu-shun-xu-shi-qi-4