题解 | #调整数组顺序使奇数位于偶数前面(一)#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        //方法一：暴力解法，两次遍历数组，第一次遍历,寻找出奇数；第二次遍历,寻找出偶数。
        //时间复杂度：O(n^2),空间复杂度：O(n)
//         int length = array.length;
//         int[] arr = new int[length];
//         int index = 0;
//         //第一次遍历,寻找出奇数
//         for(int i=0;i<length;i++){
//             if(array[i]%2 != 0){
//                 arr[index] = array[i];
//                 index++;
//             }
//         }
        
//         //第二次遍历,寻找出偶数
//         for(int i=0;i<length;i++){
//             if(array[i]%2 == 0){
//                 arr[index] = array[i];
//                 index++;
//             }
//         }
        
//         return arr;
        
        //方法二，数组合并，遍历一次原数组，将奇数和偶数分成两个链表,最后将链表转换为数组。
        //时间复杂度：O(n^2),空间复杂度：O(n)
        ArrayList<Integer> list1 = new ArrayList<>();//存放奇数的链表
        ArrayList<Integer> list2 = new ArrayList<>();//存放偶数的链表
        int length = array.length;
        //遍历，找出奇数和偶数
        for(int i=0;i<length;i++){
            if(array[i]%2==0){
                list2.add(array[i]);
            }else{
                list1.add(array[i]);
            }
        }
        
        list1.addAll(list2);//合并链表
        Object[] obj = list1.toArray();//链表转化为数组，但是不可以直接转换为整形数组，先转换为object类型，然后再一个个转换为整形
        for(int i=0;i<length;i++){
            array[i] = (int)obj[i];
        }
        return array;
    }
}