奇偶排序-在线编程-K6K4.com

给定一个随机整数序列，请调整数字的顺序，使得所有的奇数排在偶数前面，且奇数之间的原有顺序不变，偶数之间的原有顺序也不变。
要求：时间复杂度O(n)

输入、输出描述

输入：

arr: 随机整数数组
n: 数组长度

输出：

排好序的数组

Example

输入：

arr=[3,1,6,2,9,4,7]
n=7

输出：

[3,1,9,7,6,2,4]

代码：

import java.util.*;

public class Main {

 

 public int[] solution(int[] arr,int n) {


	 List<Integer> list = new ArrayList<Integer>();
        List<Integer> list2 = new ArrayList<Integer>();

        for (int i = 0; i < n; i++) {
           
            if (arr[i] %2 != 0){
                list.add(arr[i]);
            }else {
                list2.add(arr[i]);
            }
        }
        list.addAll(list2);
        int i = 0;
        for(int s :list){
            arr[i] = s;
            i++;
        }


        return arr;
    }
}