首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面(一)
  • 热度指数：105855 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

数据范围：，数组中每个数的值
要求：时间复杂度 ，空间复杂度
进阶：时间复杂度 ，空间复杂度
示例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]
算法知识视频讲解
添加回答
牛客247459291号头像 牛客247459291号
循环一次
遇到偶数奇数这种组合
就交换位置
然后比较交换后还需不需要继续交换
public int[] reOrderArray (int[] array) {

        // write code here
        for (int i = 0;i < array.length - 1 ;i++ ){
            while ( i>=0 &&array[i] % 2 == 0 && array[i+1] % 2 == 1 ){
              int temp =  array[i];
              array[i] = array[i+1];
              array[i+1] = temp;
              i--;
            }
        }
        return array;
    }
发表于 2021-03-17 21:25:46 回复(1)
Java
阿尼亚瓦库瓦库头像 阿尼亚瓦库瓦库 
//很简单的两遍遍历，结果却很慢。。还好过了
public int[] reOrderArray (int[] array) {

        int count = 0;

        for (int i = 0; i < array.length; i++) {
            if (array[i]%2 == 1) {
                count ++;
            }
        }

        int[] result = new int[array.length];
        int sig = 0;
        int dou = count;
        for (int i = 0; i < array.length; i++) {
            if (array[i]%2 == 1) {
                result[sig++] = array[i];
            } else {
                result[dou++] = array[i];
            }
        }

        return result;
    }

发表于 2021-05-01 23:59:20 回复(1)
比杨德布鲁头像 比杨德布鲁

选择具有稳定性的排序方法, 例如冒泡

 public int[] reOrderArray (int[] array) {
        // bubble sort
        if (array == null || array.length == 0) return new int[0];
        int n = array.length; 
        boolean changed = true;

        for (int i=n-1; i>0 && changed; i--) {
            changed = false;
            for (int j=0; j<i; ++j) {
                // 左边是偶数, 右边是奇数的情况
                if ((array[j] & 1) == 0 && (array[j+1] & 1) == 1) {
                    changed = true;
                    int tmp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = tmp;
                }
            }
        }       
        return array;
    }
}
发表于 2021-02-26 22:53:03 回复(1)
C++
Spectre_头像 Spectre_ 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // 时间复杂度O(N)，空间复杂度O(1)
        vector<int> res(array.size(), 0);
        int ind = 0;
        for (int i = 0; i < array.size(); ++i)
            if (array[i] & 1) res[ind++] = array[i];
        for (int i = 0; i < array.size(); ++i) 
            if (!(array[i] & 1)) res[ind++] = array[i];
        return res;
    }
};

发表于 2022-08-17 23:41:04 回复(0)
C
Duoni头像 Duoni 
typedef struct SL//定义一个结构体模板
{
    int* vate;//int指针/数组
    int size;//实际数位计数
    int capecity;//空间大小
}SL;

void init(SL* tr)//初始化
{
    tr->vate = NULL;
    tr->capecity = tr->size = 0;
}

void rea_cp(SL* tr)//扩容
{
    int new_capecity = tr->capecity == 0 ? 4 : tr->capecity * 2;
    int* tep = (int*)realloc(tr->vate, sizeof(int)*new_capecity);
    tr->vate = tep;
    tr->capecity = new_capecity;
}

int* reOrderArray(int* array, int arrayLen, int* returnSize ) 
{
    // write code here
    SL tr_1, tr_2;//声明两个结构体对象
    init(&tr_1);//初始化两个结构体
    init(&tr_2);
    for(int i = 0; i<arrayLen; i++)//区分
    {
        if(array[i] % 2 == 0)//偶数放在tr_2中
        {
            if(tr_2.size == tr_2.capecity)//检查空间
            {
                rea_cp(&tr_2);
            }
            tr_2.vate[tr_2.size++] = array[i];
        }
        else//奇数放在tr_1中
        {
            if(tr_1.size == tr_1.capecity)//检查空间
            {
                rea_cp(&tr_1);
            }
            tr_1.vate[tr_1.size++] = array[i];
        }
    }
    if(tr_2.size == arrayLen)//若偶数组等于原数组数位，则代表全是偶数，返回
    {
        *returnSize = tr_2.size;
        return tr_2.vate;
    }
    if(tr_1.size == arrayLen)//若基数组等于原数组数位，则代表全是奇数，返回
    {
        *returnSize = tr_1.size;
        return tr_1.vate;
    }
    for(int j = 0; j < tr_2.size; j++)//如果不是以上，则将偶数组元素插入倒奇数组后
    {
        if(tr_1.size == tr_1.capecity)//检查扩容
        {
            rea_cp(&tr_1);   
        }
        tr_1.vate[tr_1.size++] = tr_2.vate[j];//倒数
    }
    *returnSize = tr_1.size;//返回
    return tr_1.vate;
}

发表于 2022-08-14 23:05:11 回复(0)
C
赶紧离职头像 赶紧离职
int* reOrderArray(int* array, int arrayLen, int* returnSize ) {
    // write code here
    int i=0,j=0;
    int *a=(int *)malloc(sizeof(int)*arrayLen);
    * returnSize=arrayLen;
    for(i=0;i<arrayLen;i++){
        if(array[i]%2!=0){a[j++]=array[i];}//奇数
    }
    for(i=0;i<arrayLen;i++){
        if(array[i]%2==0){a[j++]=array[i];}//偶数
    }
    return a;
}
发表于 2021-11-15 23:43:49 回复(0)
Java
胖乎乎的蚊不叮很热爱生活头像 胖乎乎的蚊不叮很热爱生活
简简单单就好，不要搞得花里胡哨 
public int[] reOrderArray (int[] array) {
        int[] temp = new int[array.length];
        int i,j = 0;
        for(i = 0;i<array.length;i++){
            if(array[i]%2!=0){
                temp[j] = array[i];
                j++;
            }
        }
        for(i = 0;i<array.length;i++){
            if(array[i]%2==0){
                 temp[j] = array[i];
                j++;
            }
        }
        return temp;
        // write code here
    }


发表于 2021-08-22 23:07:14 回复(0)
Java
牛客659554380号头像 牛客659554380号
    public int[] reOrderArray (int[] array) {
        // write code here
        int[] resArr = new int[array.length];
        //int[] evenArr = 
        //第一次遍历
        int count=0;
        for(int i= 0;i<array.length; i++)
        {
            //如果是奇数
            if(array[i]%2!=0)
            {
               resArr[count++] = array[i];
            }
        }
        //第二次遍历
       for(int i= 0;i<array.length; i++)
        {
            //如果是偶数
            if(array[i]%2==0)
            {
               resArr[count++] = array[i];
            }
        }
        return resArr;
    }
}
发表于 2021-08-08 00:03:04 回复(0)
Python 3
zxupstar头像 zxupstar
python 送分题 
class Solution:
    def reOrderArray(self , array ):
        new1 = []
        new2 = []
        for i in range(len(array)):
            if array[i]%2 == 1: new1.append(array[i])
            else :              new2.append(array[i])
        return new1 + new2


发表于 2021-07-31 21:04:52 回复(0)
JavaScript Node
webchang头像 webchang
使用JavaScript实现

方法1

新创建一个奇数数组odd和偶数数组even。遍历原数组，如果是偶数就添加到偶数数组中；如果是奇数就添加到奇数数组中。最后将奇数数组和偶数数组合并 
function reOrderArray( array ) {
    // write code here
    let odd = [];
    let even = [];
    array.forEach(num => {
        if(num % 2 === 0) {
            even.push(num);
        } else {
            odd.push(num);
        }
    });
    return odd.concat(even);
}

方法2

方法2和方法1的原理相同。使用了数组的filter方法，看起来比方法1要简洁 
function reOrderArray( array ) {
    // write code here
    let even = array.filter(n => n % 2 === 0);
    let odd = array.filter(n => n % 2 === 1);
    return odd.concat(even);
}

方法3

新创建一个数组，同时设定一个“指针”indexHead，初始值为0。遍历原数组，如果是偶数就直接push进新数组中；如果是奇数，使用splice方法将奇数插入到新数组的indexHead位置，然后让indexHead的值加1 
function reOrderArray( array ) {
    // write code here
    let indexHead = 0;
    let resultArr = [];
    for(let i = 0;i < array.length;i++) {
        if(array[i] % 2 === 0) {
            resultArr.push(array[i]);
        } else {
            resultArr.splice(indexHead,0,array[i]);
            indexHead++;
        }
    }
    return resultArr;
}

方法4

新创建一个数组。遍历原数组，如果是奇数就直接push进新数组中，然后将该奇数从数组中移除；如果是偶数，直接跳过进行下一次循环。循环结束后原数组剩下的元素就全是偶数了。然后让两个数组合并
function reOrderArray( array ) {
    // write code here
    let result = [];
    for(let i = 0;i < array.length;i++) {
        if(array[i] % 2 !== 0) {
            result.push(array[i]);
            array.splice(i,1);
            i--;
        }
    }
    return result.concat(array)
}





发表于 2021-07-24 15:23:19 回复(2)
JavaScript
你有尾巴吗头像 你有尾巴吗 
array.sort((a,b)=>{
	let aa=a%2;
	let bb= b%2;
	if(aa==bb){
		return 0
	}else{
	return bb-aa
	}
})
return array;

发表于 2021-06-06 16:38:54 回复(0)
Python
吾三省啊头像 吾三省啊
遍历数组 将偶数移到数组尾部 
class Solution:
    def reOrderArray(self , array ):
        # write code here
        l = len(array)
        low = 0
        while low <=l-1:
            if array[low] %2 ==0:
                temp = array.pop(low)
                array.append(temp)
                l -=1
            else:
                low +=1
        return array
发表于 2021-04-26 17:27:38 回复(0)
心灵蚂蚁头像 心灵蚂蚁 
import java.util.*;


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

		List<Integer> odd = new ArrayList<>();
		List<Integer> even = new ArrayList<>();
		List<Integer> res = new ArrayList<>();

		for (int i = 0; i < array.length; i++) {
			if (array[i] % 2 == 0) {
				even.add(array[i]);
			} else {
				odd.add(array[i]);
			}
		}
		odd.forEach(i -> res.add(i));
		even.forEach(i -> res.add(i));
		return res.stream().mapToInt(i -> i).toArray();
    }
}





发表于 2021-03-31 22:10:16 回复(2)
牛客646969259号头像 牛客646969259号 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArray(vector<int>& array) {
        // write code here
        int len=array.size();
        for(int i=0;i<len;){
            if(array[i]%2==0){
                int temp=array[i];
                for(int j=i+1;j<array.size();j++){
                    array[j-1]=array[j];
                }
                --len;
                array[array.size()-1]=temp;
            }else{
                i++;
            }
        }
        return array;
        
    }
};
遍历，遇到偶数就把剩下部分前移，偶数置于最后。
发表于 2021-03-27 16:16:20 回复(0)
JavaScript
IPzzzi头像 IPzzzi 
function reOrderArray( array ) {
    // write code here
    var arr1 = [];
    var arr2 = [];
    for(var i = 0;i<array.length;i++){
        if(array[i] % 2 != 0){
            arr1.push(array[i]);
        }else{
            arr2.push(array[i]);
        }
    }
    return arr1.concat(arr2);
}

发表于 2021-03-16 21:44:23 回复(0)
JavaScript
别卷啦！头像 别卷啦！
由于需要考虑到调整之后的稳定性，因此我们可以使用辅助数组的方式。首先对数组中的元素进行遍历，每遇到一个奇数就将它加入到 奇数辅助数组中，每遇到一个偶数，就将它将入到偶数辅助数组中。最后再将两个数组合并。这一种方法的时间复杂度为 O(n)，空间 复杂度为 O(n)。 
function reOrderArray( array ) {
    // write code here
    let arr1 = [],arr2 = []
    for(let item of array){
        if(item % 2 == 0) arr2.push(item)
        else arr1.push(item)
    }
    return arr1.concat(arr2)
}

发表于 2021-03-11 17:04:00 回复(0)
Java
重剑无锋zcy头像 重剑无锋zcy 
import java.util.*;


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

        return result;
    }
}


发表于 2021-03-03 10:48:29 回复(1)
Python
食堂在逃干饭王头像 食堂在逃干饭王 
class Solution:
    def reOrderArray(self , array ):
        # 不定义新空间的话，用冒泡
        for i in range(len(array)-1, -1, -1):
            for j in range(i):
                if(array[j] %2 == 0 and array[j+1] % 2 != 0):
                    array[j], array[j+1] = array[j+1], array[j]
        return array

发表于 2021-03-01 14:25:56 回复(1)
dwzhu头像 dwzhu 
class Solution:
    def reOrderArray(self , array ):
        # write code here
        odd, even = [], []
        for i in range(len(array)):
            if array[i]%2==1:
                odd.append(array[i])
            else:
                even.append(array[i])
        return odd+even

发表于 2021-02-26 12:46:17 回复(0)
alpha0x00头像 alpha0x00

第一种，时间 O(n)，空间 O(n)

扫描两遍复制到数组即可 

vector<int> reOrderArray(vector<int>& arr)
{
    vector<int> ret(arr.size());
    int idx = 0;
    for (auto num : arr) {
        if (num&1)
            ret[idx++] = num;
    }
    for (auto num : arr) {
        if (!(num&1))
            ret[idx++] = num;
    }    
    return ret;
}

第二种，本质上是排序 (奇数小于偶数)，而且是稳定的排序

可以采用 插入排序、冒泡排序、归并排序、基数排序 等 稳定 排序算法 

stable_sort(arr.begin(), arr.end(), [](int a, int b) -> bool {
    return a&1 && !(b&1);
});
编辑于 2021-05-15 10:54:19 回复(0)
提交观点

问题信息

数组
上传者：牛客301499号
难度：
219条回答 6938浏览

热门推荐

通过挑战的用户

查看代码

相关试题

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

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号