# Partition Array by Odd and Even ### Source - lintcode: [(373) Partition Array by Odd and Even](http://www.lintcode.com/en/problem/partition-array-by-odd-and-even/) - [Segregate Even and Odd numbers - GeeksforGeeks](http://www.geeksforgeeks.org/segregate-even-and-odd-numbers/) ~~~ Partition an integers array into odd number first and even number second. Example Given [1, 2, 3, 4], return [1, 3, 2, 4] Challenge Do it in-place. ~~~ ### 题解 将数组中的奇数和偶数分开，使用『两根指针』的方法最为自然，奇数在前，偶数在后，若不然则交换之。 ### Java ~~~ public class Solution { /** * @param nums: an array of integers * @return: nothing */ public void partitionArray(int[] nums) { if (nums == null) return; int left = 0, right = nums.length - 1; while (left < right) { // odd number while (left < right && nums[left] % 2 != 0) { left++; } // even number while (left < right && nums[right] % 2 == 0) { right--; } // swap if (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; } } } } ~~~ ### 源码分析 注意处理好边界即循环时保证`left < right`. ### 复杂度分析 遍历一次数组，时间复杂度为 O(n)O(n)O(n), 使用了两根指针，空间复杂度 O(1)O(1)O(1).