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

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

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

思路

• 先遍历数组，计算奇数的个数
• 再新建等长数组，双指针：奇数 < - > 偶数
• 遍历原数组，若是奇数，放于奇数指针指向的位置，指针向后移动；若是偶数，放于偶数指针指向的位置，指针向后移动
• 将新数组copy至原数组

代码

public class Solution {
    public void reOrderArray(int [] array) {
        if (array.length <= 1)
            return;
        
        int oddBegin = 0;
        int oddCount = 0;
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1)
                oddCount++;
        }
        
        int[] result = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if ((array[i] & 1) == 1)
                result[oddBegin++] = array[i];
            else
                result[oddCount++] = array[i];
        }
        
        for (int i = 0; i < array.length; i++) {
            array[i] = result[i];
        }
    }
}