ZYF010 调整数组顺序使所有奇数位于偶数前面
大约 3 分钟
ZYF010 调整数组顺序使所有奇数位于偶数前面
【算法】 双指针
【C++】 双指针、swap
【难度】 入门
一、题目简述
给定一个长度为 的整数数组,要求通过交换操作,将所有奇数移到所有偶数的前面(奇数之间、偶数之间的相对顺序可以改变)。求最少交换次数。
二、解题思路
算法选择:双指针
题目要求将奇数全部放在前面,偶数全部放在后面,并且要求交换次数最少。这个问题可以使用双指针优雅地解决。
核心思路:用两个指针分别从两端向中间扫描。
- 左指针 :从左往右找偶数(因为在左边但应该是奇数的位置出现了偶数,需要把它换到右边去)。
- 右指针 :从右往左找奇数(因为在右边但应该是偶数的位置出现了奇数,需要把它换到左边去)。
- 当 时,交换
a[l]和a[r],计数加一。这样一次交换就把一对"错位"的奇偶放到了正确的位置。
为什么这是最少的交换次数?因为每次交换都同时解决了两个位置的问题(一个本应是奇数的位置上的偶数,和一个本应是偶数的位置上的奇数),属于最"高效"的操作。
具体实现
- 初始化 (从第 1 个位置开始),(从最后一个位置开始),。
- 当 时循环:
- 不断右移,直到遇到偶数(或 )。
- 不断左移,直到遇到奇数(或 )。
- 如果 ,交换
a[l]和a[r],++。
- 输出 。
手动模拟
以数组 [1, 2, 3, 4, 5] 为例:
| 步骤 | l | r | a[l] | a[r] | 操作 | 数组变化 | cnt |
|---|---|---|---|---|---|---|---|
| 初始 | 1 | 5 | — | — | — | [1,2,3,4,5] | 0 |
| 1 | 1 | 5 | 1(奇),继续 | — | l++ | — | 0 |
| 2 | 2 | 5 | 2(偶),停 | — | — | — | 0 |
| 3 | 2 | 5 | — | 5(奇),停 | — | — | 0 |
| 4 | 2 | 5 | — | — | swap a[2]和a[5] | [1,5,3,4,2] | 1 |
| 5 | 3 | 4 | 3(奇),继续 | — | — | — | 1 |
| 6 | 4 | 4 | 4(偶),停 | — | — | — | 1 |
| 7 | 4 | 4 | l=r | — | 循环结束 | — | 1 |
最终数组为 [1, 5, 3, 4, 2],交换次数为 1。
再以数组 [2, 4, 6, 1, 3, 5] 为例(全部偶数在前、奇数在后):
| 步骤 | l | r | 操作 | 数组变化 | cnt |
|---|---|---|---|---|---|
| 初始 | 1 | 6 | — | [2,4,6,1,3,5] | 0 |
| 1 | 1 | 6 | l=1 偶, r=6 奇, swap | [5,4,6,1,3,2] | 1 |
| 2 | 2 | 5 | l=2 偶, r=5 奇, swap | [5,3,6,1,4,2] | 2 |
| 3 | 3 | 4 | l=3 偶, r=4 奇, swap | [5,3,1,6,4,2] | 3 |
| 4 | 4 | 3 | l>r, 结束 | — | 3 |
交换 3 次,最终数组 [5, 3, 1, 6, 4, 2],所有奇数在前。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
int l = 1, r = n, cnt = 0;
while (l < r) {
// 左指针找偶数
while (l < r && a[l] % 2 == 1) l++;
// 右指针找奇数
while (l < r && a[r] % 2 == 0) r--;
// 交换
if (l < r) {
swap(a[l], a[r]);
cnt++;
}
}
cout << cnt << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。两个指针各自最多移动 步,每个元素最多被访问常数次。
- 空间复杂度:(存储数组)。如果只求交换次数而不需要输出最终数组,空间可优化为 (直接在输入上操作)。
知识扩展
双指针(Two Pointers)是一种非常实用的技巧,常见的形式有:
- 对撞指针(本题):两端向中间移动,常用于分区问题。
- 快慢指针:一快一慢同向移动,常用于找链表环、去重等。
- 滑动窗口:维护一个满足条件的区间,常用于子数组问题。
