剑指Offer(21) 调整数组顺序使奇数位于偶数前面

发表于 | 分类于 | 阅读次数:
字数统计: 496 | 阅读时长 ≈ 2

调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

思路

对于任意一个整数数组，设置一个left指针，从前往后走，如果遇到奇数则指针后移，遇到偶数时，指针停止；设置一个right指针，从前往后走，遇到偶数时指针前移，遇到奇数是，可以喝前面的指针所指的偶数进行调换。

测试用例

  1. 功能测试（数组中奇偶交替出现、数组中先奇后偶、先偶后奇）
  2. 特殊测试（null、空数组、一个数据的数组）

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ReorderArray {
	public void reorderArray(int[] arr) {
		if (arr == null || arr.length <= 0)
			return;
		int left = 0;
		int right = arr.length - 1;
		int tmp;
		while (left < right) {
			while (left < right && (arr[left] & 1) != 0)
				left++;
			while (left < right && (arr[right] & 1) == 0)
				right--;
			tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
		}
	}
}

附加要求

如果题目附加要求：保证调整后的数组中，奇数和奇数之间，偶数和偶数之间的相对位置不变。
此时用上面的方法无法实现该功能，可以采用类似于“直接插入排序”的方法：从头开始遍历，遇到奇数时，将该奇数插入到该奇数前面的偶数之前。（如：从头开始遍历246183，遇到奇数1时，将1插入到246之前，变为：124683；该插入的实质是：奇数前面的所有偶数往后移一位，空出的位置放入该奇数）

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void reorderArray1(int[] arr) {
	if (arr == null || arr.length <= 0)
		return;

	int tmp, j;
	for (int i = 1; i < arr.length; i++) {
		if ((arr[i] & 1) != 0) {
			j = i;
			tmp = arr[i];
			while ((j > 0) && (arr[j - 1] & 1) == 0) {
				arr[j] = arr[j - 1];
				j--;
			}
			arr[j] = tmp;
		}
	}
}
0%