奇偶分割数组

题意

分割一个整数数组,使得奇数在前偶数在后。

样例

给定 [1, 2, 3, 4],返回 [1, 3, 2, 4]

思路

两个指针分别从数组两端开始查找,左侧指针依次向右找直到遇到一个偶数为止,右侧指针依次向左找直到遇到一个奇数为止。然后将这两个数置换,然后左右两个指针继续向中间查找,直到两个指针碰头为止。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
/**
* @param nums: an array of integers
* @return: nothing
*/
public void partitionArray(int[] nums) {
int start = 0;
int end = nums.length - 1;
while (start < end) {
while (start < end && nums[start] % 2 == 1) {
start++;
}
while (start < end && nums[end] % 2 == 0) {
end--;
}
if (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
}

原题地址

LintCode:奇偶分割数组

坚持原创技术分享,您的支持将鼓励我继续创作!