首页 > 试题广场 >

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

[编程题]调整数组顺序使奇数位于偶数前面(一)
  • 热度指数:102216 时间限制: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]
最普通的解法,直接挨个遍历
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArray (int[] array) {
        ArrayList<Integer> oddList = new ArrayList<>();
        ArrayList<Integer> evenList = new ArrayList<>();
        int[] res = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if (0 == array[i] % 2) {
                // 偶数
                evenList.add(array[i]);
            } else {
                // 奇数
                oddList.add(array[i]);
            }
        }
        for (int i = 0; i < oddList.size(); i++) {
            res[i] = oddList.get(i);
        }
        int index = oddList.size();
        for (int i = 0; i < evenList.size(); i++) {
            res[index] = evenList.get(i);
            index++;
        }
        return res;
    }
}


发表于 2021-02-25 22:42:51 回复(3)
循环一次
遇到偶数奇数这种组合
就交换位置
然后比较交换后还需不需要继续交换
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)
//很简单的两遍遍历,结果却很慢。。还好过了
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)
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)
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)
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)
简简单单就好,不要搞得花里胡哨
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)
    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 送分题
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实现

方法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)
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)
遍历数组 将偶数移到数组尾部 
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)
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)
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)
由于需要考虑到调整之后的稳定性,因此我们可以使用辅助数组的方式。首先对数组中的元素进行遍历,每遇到一个奇数就将它加入到 奇数辅助数组中,每遇到一个偶数,就将它将入到偶数辅助数组中。最后再将两个数组合并。这一种方法的时间复杂度为 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)
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)
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)
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)