[13] 调整数组顺序使奇数位于偶数前面(中等)
[13] 调整数组顺序使奇数位于偶数前面(中等)

题目描述

输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
输入:[1,2,3,4]
返回值:[1,3,2,4]
输入:[2,4,6,5,7]
返回值:[5,7,2,4,6]

解题思路

暴力法

直接遍历一次数组,如果是奇数则存到奇数集合中,如果是偶数则存到偶数集合中。
/**
 * 暴力法
 * T(n) S(n)
 */
public int[] reOrderArray (int[] array) {
    List<Integer> odd = new ArrayList<>();
    List<Integer> even = new ArrayList<>();
    for (int i : array) {
        if (i % 2 == 0) {
            even.add(i);
        } else {
            odd.add(i);
        }
    }
    odd.addAll(even);
    return odd.stream().mapToInt(Integer::intValue).toArray();
}

双指针

通过 lr 两个快慢双指针遍历数组,当 l 指向奇数时 l 往前走一步,r 指向偶数时 r 往前走一步,如果 l 指向偶数 r 指向奇数则交换,交换完成后判断 lr 之间是否全是偶数,全是偶数则需要依次交换还原偶数序列的顺序。
这个解法在牛客网超时了,因为存在全偶数段时需要依次交换,如果情况恶劣,则不如暴力法来的直接。
/**
 * 快慢双指针
 * T(n^2) S(1)
 */
public static int[] reOrderArray(int[] array) {
    int l = 0;
    int r = 1;
    int t = -1;
    // 通过 l 和 r 两个快慢双指针遍历数组
    while (l < r && l < array.length && r < array.length) {
        // 如果 l 指向偶数 r 指向奇数则交换
        if (array[l] % 2 == 0 && array[r] % 2 != 0) {
            int temp = array[r];
            array[r] = array[l];
            array[l] = temp;
            l++;
            // 判断 l 和 r 之间是否是全偶数段
            while (t != -1 && t < r) {
                // 将所有偶数一次交换保证原顺序
                temp = array[t];
                array[t] = array[r];
                array[r] = temp;
                t++;
            }
            t = -1;
        }
        // 当 l 和 r 都指向偶数时,t 指向全偶数段的起始位置
        if (array[l] % 2 == 0 && array[r] % 2 == 0 && l != r) {
            t = l + 1;
        }
        // l 指向奇数时 l 往前走一步
        if (array[l] % 2 != 0) {
            l++;
        }
        // r 指向偶数时 r 往前走一步
        if (array[r] % 2 == 0) {
            r++;
        }
    }
    return array;
}