剑指Offer_13

发表于 | 分类于

题目

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

解题思路

解法一：
时间复杂度高O(n^2)，但是不占额外的内存空间

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
26
27
28
29
public class Solution {
    private void exchange(int []array, int i, int j){
        int temp = array[i]; 
        array[i] = array[j];
        array[j] = temp;
    }
    
    private boolean isOdd(int x){
        return x % 2 == 1;
    }
    
    private boolean isEven(int x){
        return x % 2 == 0;
    }
    
    public void reOrderArray(int [] array) {
        if(array == null || array.length == 0){
            return;
        }
        //冒泡算法，将后置位的奇数和它的前值位的偶数进行顺序交换
        for(int i = 1; i < array.length; ++i){
            for(int j = i; j > 0 && isEven(array[j-1]) && isOdd(array[j]); --j){
                exchange(array, j-1, j);
            }
        }
    }
    
    
}

解法二：
时间复杂度和空间复杂度都为O(n)
两个数组分别储存奇数和偶数

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
26
27
public class Solution {
    public void reOrderArray2(int [] array) {
        if(array == null || array.length == 0){
            return;
        }
        List<Integer> oddList = new ArrayList<>();
        List<Integer> evenList = new ArrayList<>();
        for(int i = 0; i < array.length; ++i){
            if(isOdd(array[i])){
                oddList.add(array[i]);
            }
            else{
                evenList.add(array[i]);
            }
        }
        for(int i = 0; i < oddList.size(); ++i){
            array[i] = oddList.get(i);
        }
        //array[i]的位置记得加上odd.size()
        for(int i = 0; i < evenList.size(); ++i){
            array[oddList.size() + i] = evenList.get(i);
        }
    }
}