每日算法之调整数组顺序使奇数位于偶数前面(二)

描述

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

相关问答

Q1: 方法1

思路：

既然要把所有的奇数放在数组前面，所有的偶数放在数组后面，那可以统计奇数在原数组中出现了多少次，这样就可以找到二者的分界线。有了分界线以后，前面就是奇数，后面就是偶数，可以利用两个指针分别指向二者的开头，遇到一个元素就添加到相应位置，然后指针移动。（该方法保证了相对位置不变）

代码

public int[] reOrderArrayTwo (int[] array) {
        // write code here
        if (array.length <= 0) return new int[0];
        int[] result = new int[array.length];
        int y = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) y++;
        }
        int x = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                result[x] = array[i];
                x++;
            }
            if (array[i] % 2 == 0) {
                result[y] = array[i];
                y++;
            }
        }
        return result;
    }

Q2: 方法2

思路

这道题不需要要求相对位置不变，因此我们可以采用位置交换的方法，只要奇数全部换到前面就可以了。利用左右双指针分别从数组首尾出发向中间走，交换其中的偶数在前奇数在后的情况。（该方法不能保证相对位置不变）

代码

package esay.JZ81调整数组顺序使奇数位于偶数前面2;

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    //方法1
    /*public int[] reOrderArrayTwo (int[] array) {
        // write code here
        if (array.length <= 0) return new int[0];
        int[] result = new int[array.length];
        int y = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) y++;
        }
        int x = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 1) {
                result[x] = array[i];
                x++;
            }
            if (array[i] % 2 == 0) {
                result[y] = array[i];
                y++;
            }
        }
        return result;
    }*/
    //方法2
    public int[] reOrderArrayTwo(int[] array) {
        // write code here
        int i = 0;
        int j = array.length - 1;
        while (i < j) {
            //左边奇数，右边偶数
            if (array[i] % 2 == 1 && array[j] % 2 == 0) {
                i++;
                j--;
            }
            //左右全是奇数
            else if (array[i] % 2 == 1 && array[j] % 2 == 1) {
                i++;
            }
            //左边偶数，右边奇数
            else if (array[i] % 2 == 0 && array[j] % 2 == 1) {
                int temp = array[j];
                array[j] = array[i];
                array[i] = temp;
            }
            //左右全是偶数
            else {
                j--;
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 2, 3, 4};
        System.out.println(Arrays.toString(new Solution().reOrderArrayTwo(arr)));
    }
}