【剑指Offer】调整数组顺序使奇数位于偶数前面

Posted on | In ,

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

只完成基本功能的解法，仅适用于初级程序员

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void reOrderArray(int[] array) {
    int begin = 0;
    int end = array.length - 1;

    while (begin < end){
        while (begin < end && (array[begin] & 1) == 1)
            begin++;

        while (begin < end && (array[end] & 1) != 1)
            end--;

        if (begin < end){
            int tmp = array[end];
            array[end] = array[begin];
            array[begin] = tmp;
        }
    }
}

考虑可扩展性的解法，能秒杀Offer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void reOrderArray(int[] array) {
    int begin = 0;
    int end = array.length - 1;

    while (begin < end){
        while (begin < end && isOdd(array[begin]))
            begin++;

        while (begin < end && !isOdd(array[end]))
            end--;

        if (begin < end){
            int tmp = array[end];
            array[end] = array[begin];
            array[begin] = tmp;
        }
    }
}

private boolean isOdd(int n){
    return (n & 1) == 1;
}

本题扩展

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

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void reOrderArray(int[] array) {
    int[] aux = new int[array.length];
    int countOdd = 0;

    for (int i = 0; i < array.length; i++) {
        aux[i] = array[i];

        if (isOdd(array[i]))
            countOdd++;
    }

    int oddPos = 0;
    int evenPos = countOdd;

    for (int i = 0; i < aux.length; i++){
        if (isOdd(aux[i]))
            array[oddPos++] = aux[i];
        else
            array[evenPos++] = aux[i];
    }
}

private boolean isOdd(int n){
    return (n & 1) == 1;
}