剑指 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，不然编译出错。