调整数组顺序使奇数在前偶数在后

1.题目:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
2.思路:
方法一:使用队列先进先出特点,将奇数偶数分开,再合并。

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int len=array.length;
        int[] res=new int[len];//创建一个相等长的数组
        int index=0;
        Queue<Integer> odd=new LinkedList<>();//队列的链表(因为个数未知)来存储偶数
        for(int i=0;i<len;i++){//奇数直接入数组
            if(array[i]%2==1){
                res[index]=array[i];
                index++;
            }else{//偶数直接入队列
                odd.add(array[i]);
            }
        }
        while(!odd.isEmpty()){//将偶数出队进数组
            res[index]=odd.poll();
            index++;
        }
        return res;
    }
}

时间复杂度:O(n)
方法二:

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        int len=array.length;
        if(array==null||len==0) return new int[0];
        for(int i=0;i<len;++i){ //++1这样刚好到len-1,后面的i+1就不会越界
            for(int j=0;j<len-i-1;j++){//
                if((array[j]&1)==0&&(array[j+1]&1)==1){
                    int temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
        return array;
    }
}
全部评论

相关推荐

虚闻松声:简历看起来很清爽。几点建议。 1. 总结提炼项目工作内容。如第一个项目第一点,研发用户信息管理、购票功能:(然后具体展开)。还可以继续总结,如基础功能开发、算法优化座位分配、并发性能提升等等 2. 优化技术栈描述。全文多次出现Spring Boot,我感觉一次就够了。可以不写或者写整个体技术架构? 3. 增加业务指标描述。最好有一些业务效果的指标。或者优化的效果指标等等。
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
03-10 14:27
已编辑
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务