# 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).