Blog
私有云
聊天室
图床
登录
[TOC]
Acwing 32. 调整数组顺序使奇数位于偶数前面
作者：
linzy
浏览：128
2021年3月22日 21:35
### Acwing 32. 调整数组顺序使奇数位于偶数前面 #### 题目链接： [Acwing 32. 调整数组顺序使奇数位于偶数前面](https://www.acwing.com/problem/content/30/) #### 解题思路：双指针法O(n) 类型：左右指针法 使用两个指针，分别指向首尾，然后向中间扫描。 扫描时保证头指针扫描过的数都是奇数，尾指针扫描过的数都是偶数。如不符合条件则停止，然后头尾指针的数进行交换。 每次迭代进行的操作： 1. 第一个指针从头开始扫描直到遇到偶数则停止。*扫描过的数都是奇数* 2. 第二个指针从尾往前开始扫描，直到遇到奇数则停止。*扫描过的数都是偶数* 3. 这时如果第一个指针依旧在第二个指针的左边，则交换两个指针的值，*将奇数交换到左边，偶数交换到右边*，继续遍历直到两个指针相遇为止 **时间复杂度分析：**左右两个指针相向遍历，直到相遇，走过的总长度为n，所以时间复杂度为O(n) #### C++代码： ```c++ class Solution { public: void reOrderArray(vector<int> &array) { int i = 0; int j = array.size(); while(i < j) { while(array[i] % 2 == 1 && i < j)i++; while(array[j] % 2 == 0 && i < j)j--; if(i < j)swap(array[i],array[j]); } } }; ```
请
登录
后回复
共有0条评论
闽ICP备19009362号
linzy
浏览：128
2021年3月22日 21:35