NC77 调整数组顺序使奇数位于偶数前面 算法java实现

题目描述

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

解题思路

可以使用插入排序法，将遇到的奇数跟左边的交换位置，直到最左边为奇数为止，这里也可以将上次移动的奇数位置记下来，重复排序直到列尾，但这样的时间复杂度为O(n*n)，于是想想题目的最终结果是奇数都在最左边， 偶数都在最右边，是不是可以用前后双指针的方式，将识别到的奇数插入新数组的头部，偶数插入新数组的尾部，一次循环就做了两次判断插入，直到队列的尽头，这样的时间复杂度为o（n）

测试用例

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

代码实现

import java.util.*;


public class Solution {
    /**
        
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 代码思路：可以使用插入排序法，将遇到的奇数跟左边的交换位置，直到最左边为奇数为止，这里也可以将上次移动
      的奇数位置记下来，重复排序直到列尾，但这样的时间复杂度为O(n*n)，于是想想题目的最终结果是奇数都在最左边，
      偶数都在最右边，是不是可以用前后双指针的方式，将识别到的奇数插入新数组的头部，偶数插入新数组的尾部，一次循环
      就做了两次判断插入，直到队列的尽头，这样的时间复杂度为o（n）
     * 测试用例：[1,3,7,9],[2,4,6,8],[1,2,3,4],[2,1,4,3]
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] re=new int[array.length];
        int head=0;
        int tail=array.length-1;
        int begin=0;
        int end=array.length-1;
        while(begin<array.length){
            if(array[begin]%2!=0){
               re[head++]=array[begin];
            }
            
            begin++;
            
            if(array[end]%2==0){
               re[tail--]=array[end];
            }
            
            end--;
        }
        
        return re;
    }
}