首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面(一)

热度指数：102830 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

数据范围： $0 \le n \le 5000$ ，数组中每个数的值 $0 \le val \le 10000$

要求：时间复杂度 $O(n)$ ，空间复杂度 $O(n)$

进阶：时间复杂度 $O(n^2)$ ，空间复杂度 $O(1)$

示例1

输入

[1,2,3,4]

输出

[1,3,2,4]

示例2

输入

[2,4,6,5,7]

输出

[5,7,2,4,6]

示例3

输入

[1,3,5,6,7]

输出

[1,3,5,7,6]

算法知识视频讲解

Java

牛客839384289号

public int[] reOrderArray (int[] array) {
    // write code here
    int len=array.length ,p1=0 ,p2=len-1;
    int[] res=new int[len];
    for(int i=0;i<len;i++){
        if(array[i]%2==1){
            res[p1++]=array[i];
        }
        if(array[len-1-i]%2==0){
            res[p2--]=array[len-1-i];
        }
    }
    return res;
}

编辑于 2024-03-10 16:30:26 回复(0)

Java

脚踢字节拳打快手

有人用类似插入排序的思想，就是从左到右找奇数，往左边的‘序列’放，有个指针表示可以放的位置，放的时候该位置及其右边都往右移动。

这个应该没有我的方式好，我是类似冒泡法，外层循环是从右到左的偶数，内层是这个偶数不断与其右边的奇数交换。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param array int整型一维数组
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        for (int i = array.length - 1; i >= 0; i--) {
            int j = i;
            while (array[j] % 2 == 0 && j + 1 < array.length && array[j + 1] % 2 == 1) {
                int tmp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = tmp;
                j++;
            }
        }
        return array;
    }
}

发表于 2023-11-24 13:01:49 回复(0)

Java

SUMMERENT

import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        // write code here
        //记录偶数的个数
        int odd = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 == 0) {
                odd++;
            }
        }
        // 偶数数组
        int[] a = new int[odd];
        // 奇数数组
        int[] b = new int[array.length - odd];
        for (int i = 0,j = 0, k =0; i < array.length;i++) {
            if (array[i] % 2 == 0) {
                // 偶数
                a[k++] = array[i];
            }else {
                //奇数
                b[j++] = array[i];
            }
        }
        //新数组c
        int[] c = new int[array.length];
        //把奇数数组添加到c数组
        System.arraycopy(b,0,c,0,b.length);
        //把偶数数组添加到c数组
        System.arraycopy(a,0,c,b.length,a.length);
        return c;
    }
}

发表于 2023-06-14 16:45:40 回复(0)

Java

znfatfish

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        // start_jishu, start_oushu 
        int sj = 0, so = 0, tmp = 0;
        int len = array.length;
        boolean flag = false;
        for (int i = 0; i < len; i++){
            // 在数组最前面的奇数不处理
            if (!flag && array[i]%2 == 1) continue;
            // 找到数组第一个偶数的下标 so
            if (!flag) {
                flag = true;
                so = i;
                continue;
            }
            // 在第一个偶数后面的偶数不需要处理
            if (array[i]%2 == 0) continue;
            // 在第一个偶数后面的奇数需要前移
            tmp = array[i];
            for (int j = i-1; j >= so; j--) array[j+1] = array[j];
            array[so] = tmp;
            so++;
        }
        return array;
    }
}

发表于 2023-04-24 16:58:22 回复(0)

Java

two倩

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param array int整型一维数组

* @return int整型一维数组

public int[] reOrderArray (int[] array) {

// write code here

//要将奇数前移，为保持相对顺序不变比如1 2 3 4 5，这时3前移时，2后移 1 3 2 4 5

//5前移时 2 4 后移 1 3 5 2 4

//所以，要知道序列中第一个偶数位置 i，和这个偶数后面的第一个奇数位置j，

//这时[i,j-1]都是偶数从而找到数字交换区间

//i指向第一个偶数位置 j指向第一个奇数位置（已经排到前面的元素除外）

int i=0;

int j=0;

int flag=0;

for(;j<array.length;j++){

//如果是偶数并且是第一个偶数

if(array[j]%2==0 &&flag==0){

i=j;

flag=1;

}else if(array[j]%2==1){

//奇数这时[i,j-1]全是偶数，将偶数后移一位，arr[i]=arr[j] 从而完成交换

int tmp=array[j];

int k=j;

for(;k>i;k--){

array[k]=array[k-1];

}

array[i]=tmp;

i++;//array[i+1,j-1]现在是新的偶数区间,i++ 指向序列的第一个偶数

}

return array;

}

发表于 2022-11-25 09:39:10 回复(0)

Java

彼岸的饭碗

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        //双指针，左边的指针指向最靠左的偶数， 右指针进行遍历
        int left=-1;
        int right=0;
        int temp;
        while(right<array.length){
            if(left==-1){
                if(array[right]%2==0){
                    left=right;
                }
            }
            else{
                if(array[right]%2!=0){
                    //全部往右边平移一个单位
                    temp=array[right];
                    for(int i=right;i>left;i--){
                        array[i]=array[i-1];
                    }
                    array[left]=temp;
                    left++;   //最靠左的偶数右边挪一位
                }
            }
            right++;
        }
        return array;
    }
}

发表于 2022-07-10 11:22:29 回复(0)

Java

AgathaSeraphery

两种，一种直接写，不用双指针也行

 public int[] reOrderArray (int[] array) {
 
        int[] b = new int[array.length];
        int k = 0;
        for(int i = 0; i <array.length;++i){
             if(array[i] %2 != 0){
                b[k++] = array[i];
             }
        }
        
        for(int i = 0; i <array.length;++i){
             if(array[i] %2 == 0){
                b[k++] = array[i];
             }
        }
        
        return b;
   }

还有一种，插入排序的思想，碰到奇数将其插入到前面

        int temp = 0;
        for(int i = 0;i < array.length;++i){
            temp = array[i];
            if(array[i] %2 != 0 && i != 0){
                int j ;
                for(j = i; j>0 &&array[j-1] % 2==0;--j){
                    array[j] = array[j-1];
                }
                array[j] = temp;
            }
        }
        
        return array;

发表于 2022-06-15 22:19:14 回复(0)

Java

牛客112285422号

//和插入排序差不多
//不同点在于，在用变量j进行遍历的过程中，需要用d记录需要插入的位置（即前面数据中的偶数的位置）
public class Solution {
    public int[] reOrderArray (int[] array) {

        int d=0;
        int j=0;
        while (d<array.length&&j<array.length){
                while (j<array.length&&(array[j]&1)==0) j++;
                if(j==array.length) return array;
                int temp=array[j];
                for (int i=j-1;i>=d;i--){
                    array[i+1]=array[i];
                }
                array[d]=temp;
                //其实这里仔细想一想，还是挺妙的
                //如果是奇数，两个变量一起走，如果遇到是偶数了，d留在原地，j自己走
                //走到不是偶数位置
                //这样也保证了，d++所得到的元素，一定是偶数
                d++;
                j++;

        }
        return array;
    }
}

发表于 2022-03-23 21:28:45 回复(0)

Java

80后大叔

用2个list分别存放奇数和偶数

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        // write code here
        ArrayList<Integer> p = new ArrayList<>();
        ArrayList<Integer> q = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            if (array[i] % 2 != 0) {
                p.add(array[i]);
            } else {
                q.add(array[i]);
            }
        }
        p.addAll(q);
        int[] a = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            a[array.length-1-i] = p.get(array.length-1-i);
        }
        return a;
    }
}

发表于 2022-03-17 20:22:11 回复(0)

Java

冀十三

public int[] reOrderArray (int[] array) { // write code here  if(array.length<2){ return array;  } int x = 0;  Queue<Integer> queue = new LinkedList<>();   int[] result = new int[array.length];  for(int i = 0; i< array.length;i++){ if(array[i]%2==1){
            result[x++] = array[i];  }else{
            queue.add(array[i]);  }
    } while (!queue.isEmpty()){
        result[x++] = queue.poll();  } return result; }

发表于 2022-03-08 14:59:06 回复(0)

Java

JayChou1999

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArray (int[] array) {
// write code here
ArrayList<Integer> odd = new ArrayList<>();
ArrayList<Integer> even = new ArrayList<>();
for(int i = 0;i < array.length;i++){
if(array[i] % 2 == 0){//判断是偶数
even.add(array[i]);
}else{
odd.add(array[i]);
}
}
for (Integer even1 : even) {//往奇数集合里面加入偶数
odd.add(even1);
}
for(int i = 0;i < odd.size();i++){
array[i] = odd.get(i);
}
return array;
}
}

发表于 2022-02-25 01:08:11 回复(0)

Java

沟子

import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        if(array.length<=1) return array;
        LinkedList<Integer> list=new LinkedList<>();
        int a=0;int b=array.length-1;
        while(b>=0){
            if(array[b]%2!=0) list.addFirst(array[b]);
            b--;
        }
        while(a<=array.length-1){
            if(array[a]%2==0) list.addLast(array[a]);
            a++;
        }
        int j=0;
        while(!list.isEmpty()){
            array[j++]=list.removeFirst();
        }
        return array;
    }
}

发表于 2022-02-02 12:42:44 回复(0)

Java

牛客681385132号

求助，这个用例给的不对吧，首先题目说明数组里面不含有相同的元素，其次预期输出也未排序啊。

发表于 2022-01-26 17:49:28 回复(0)

Java

浮鸟(BAT实习ing，目标外企~)

解法1：遍历2次

import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        // 解法1：暴力
        int ret[] = new int[array.length];
        // 先处理奇数
        int index=0;
        for(int i=0;i<array.length;i++){
            if(array[i]%2==1)
                ret[index++]=array[i];
        }
        // 再处理偶数
        for(int i=0;i<array.length;i++){
            if(array[i]%2==0)
                ret[index++]=array[i];
        }
        return ret;
    }
}

解法2：冒泡

public class Solution {
    public int[] reOrderArray (int[] array) {
        // 解法2：仿照冒泡
        for(int i=0;i<array.length-1;i++){
            for(int j=0;j<array.length-i-1;j++){
                // 用j+1表示当前位,j表示上一位
                // 只有当前位是奇数，且上一位是偶数的情况下，才能swap（当前位，上一位）
                // 否则如果2位都是奇数，会发生相对位置的越位交换
                if(array[j+1]%2==1 && array[j]%2==0){
                    int temp = array[j+1];
                    array[j+1] = array[j];
                    array[j] = temp;
                }
            }
        }
        return array;
    }
}

发表于 2022-01-24 21:29:16 回复(0)

Java

牛客648894039号

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
/*方法一：先找出奇数个数，然后计算；
public int[] reOrderArray (int[] array) {
// write code here
int length = 0;
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
length++;
}
}
int[] res = new int[array.length];
int js = 0, os = 0;
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
res[js] = array[i];
js++;
} else {
res[length + os] = array[i];
os++;
}
}
return res;
}
*/
/*方法二：定义新数组，从头和尾插入*/
public int[] reOrderArray (int[] array) {
int[] res = new int[array.length];
int head = 0, tail = array.length - 1;
for(int i = 0; i < array.length; i++){
if(array[i] % 2 == 1){
res[head++] = array[i];
}
if(array[array.length - i - 1] % 2 == 0){
res[tail--] = array[array.length - i - 1];
}
}
return res;
}

}

发表于 2022-01-10 23:28:25 回复(0)

Java

牛客918004620号

java一次循环就好了，一个在前一个在后同时操作

import java.util.*;

public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArray (int[] array) {
// write code here
int [] res=new int[array.length];
int index=0;
int index_last=array.length-1;
for(int i=0;i<array.length;i++)
{
if(array[i]%2==1)
{
res[index]=array[i];
index++;
}
if(array[array.length-i-1]%2==0)
{
res[index_last]=array[array.length-i-1];
index_last--;
}
}

return res;
}
}

发表于 2022-01-08 11:46:20 回复(0)

Java

老农爱编程

public int[] reOrderArray (int[] array) {
        // write code here
        List<Integer> evennumbers = new ArrayList<Integer>();//偶数
        List<Integer> oddnumbers = new ArrayList<Integer>();//奇数
        int resArr [] = new int[array.length]; // 存放最后的元素
        int i = 0;//叠加器
        for(int res : array){
            if(res % 2 == 0){
                evennumbers.add(res);
            }else{
                oddnumbers.add(res);
            }
        }
        //最后将偶数中的数据遍历并且通过追加添加到奇数集合中
        for(int evennumber : evennumbers){
            oddnumbers.add(evennumber);
        }
        //遍历挨个取出
        for(int oddnumber : oddnumbers){
            resArr[i ++ ] = oddnumber;
        }
        return resArr;
    }

发表于 2022-01-06 11:36:08 回复(0)

Java

MechaVX

C++是O(n^2)时间,O(1)空间 4ms 432kb

Java是O(n) 时间和空间 86ms 12724kb

这是不是有点离谱？还是说是数据问题......

class Solution {
public:
    vector<int> reOrderArray(vector<int>& array) {
        int size=array.size();
        if(size<=1)
            return array;
        int p1=0,p2=0;
        while(1){
            while(p1<size&&array[p1]%2)
                ++p1;
            if(p1==size)
                break;
            while(p2<size&&!(array[p2]%2))
                ++p2;
            if(p2==size)
                break;
            if(p1>p2)
                ++p2;
            else{
                int temp=array[p2];
                for(int i=p2;i>p1;--i)
                    array[i]=array[i-1];
                array[p1]=temp;
            }
        }
        return array;
    }
};

import java.util.*;
public class Solution {
    public int[] reOrderArray (int[] array) {
        int len=array.length;
        if(len<=1)
            return array;
        int[]result=new int[len];
        int left=0,right=len-1;
        for(int i=0;i<len;++i)
            if(array[i]%2!=0)
                result[left++]=array[i];
        for(int i=right;right>=left;--i)
            if(array[i]%2==0)
                result[right--]=array[i];
        return result;
    }
}

发表于 2022-01-02 23:54:27 回复(0)

提交观点

问题信息

数组

上传者：牛客301499号

难度：

59条回答 423收藏 6204浏览

通过挑战的用户

查看代码

求求上天给我o...

2022-09-20 09:53:59
牛客31742...

2022-09-19 09:11:38
Levi丶acm

2022-09-16 17:47:34
牛客66488...

2022-09-16 10:51:42
优秀的羚羊爱健身

2022-09-16 09:36:31

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

输入

输出

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题