剑指 Offer（第2版）面试题 21：调整数组顺序使奇数位于偶数前面
剑指 Offer（第2版）面试题 21：调整数组顺序使奇数位于偶数前面
题目来源：32. 调整数组顺序使奇数位于偶数前面
解法1：遍历
最垃圾的写法。
代码：
class Solution
{
public:
void reOrderArray(vector<int> &array)
{
vector<int> odd, even;
for (int &x : array)
{
if (x % 2)
odd.push_back(x);
else
even.push_back(x);
}
int idx = 0;
for (int &x : odd)
array[idx++] = x;
for (int &x : even)
array[idx++] = x;
}
};
复杂度分析：
时间复杂度：O(n)，其中 n 是数组 array 的长度。
空间复杂度：O(n)，其中 n 是数组 array 的长度。
解法2：双指针
如果发现有偶数出现在奇数的前面，交换它们。
代码：
class Solution
{
public:
void reOrderArray(vector<int> &array)
{
int n = array.size(), i = 0, j = n - 1;
while (i < j)
{
// 向后移动 i，直到 array[i] 是偶数
while (i < j && array[i] % 2)
i++;
// 向前移动 j，直到 array[j] 是奇数
while (i < j && array[j] % 2 == 0)
j--;
if (i < j)
swap(array[i], array[j]);
}
}
};
复杂度分析：
时间复杂度：O(n)，其中 n 是数组 array 的长度。当两个指针相遇时，走过的总路程长度是 n。
空间复杂度：O(1)。
What’s more？
用函数指针，将判断独立出来，之后修改判断函数就能实现不同的排序。
class Solution
{
private:
void reOrder(vector<int> &array, bool (*func)(int))
{
if (array.empty())
return;
int n = array.size(), i = 0, j = n - 1;
while (i < j)
{
// 向后移动 i，直到 array[i] 是偶数
while (i < j && !func(array[i]))
i++;
// 向前移动 j，直到 array[j] 是奇数
while (i < j && func(array[j]))
j--;
if (i < j)
swap(array[i], array[j]);
}
}
static bool isEven(int n)
{
return n % 2 == 0;
}
public:
void reOrderArray(vector<int> &array)
{
reOrder(array, isEven);
}
};
注：isEven() 函数前要带 static，不然编译出错。
