首页 > 试题广场 >

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

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

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

输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。

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

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

示例1

输入

[1,2,3,4]

输出

[1,3,2,4]

说明

[3,1,2,4]或者[3,1,4,2]也是正确答案

示例2

输入

[1,3,5,6,7]

输出

[1,3,5,7,6]

说明

[3,1,5,7,6]等也是正确答案

示例3

输入

[1,4,4,3]

输出

[1,3,4,4]

算法知识视频讲解

Java

影的灰烬

划分的思想，如果前面的数一直为奇数就++，如果后面的数一直为偶数就--，直到遇到了不满足的情况，前面的数为偶数，后面的数为奇数，就交换他们的位置。

import java.util.*;


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

发表于 2021-10-28 22:00:39 回复(0)

Java

给生活加点糖

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo(int[] array) {
        // write code here
        // 奇数指针，从前往后遍历
        int low = 0;
        //偶数指针，从后往前遍历
        int high = array.length - 1;
        int temp = 0;
    
        while (low < high) {
            //左右都是奇数，左移右不动
            if (array[low] % 2 == 1 && array[high] % 2 == 1) {
                low++;
            }
            // 左奇数，右偶数
            else if (array[low] % 2 == 1 && array[high] % 2 == 0) {
                low++;
                high--;
            }
            // 左偶数，右奇数,交换位置
            else if (array[low] % 2 == 0 && array[high] % 2 == 1) {
                temp = array[low];
                array[low] = array[high];
                array[high] = temp;
            }
            // 左右都是偶数
            else {
                high--;
            }  
        }
        return array; 
    }
}

发表于 2022-04-23 10:43:06 回复(0)

terrancy

既要保持数组调整顺序的稳定性,又要保持时间复杂度O(N)和空间复杂度O(1).这个有点难搞哦

发表于 2022-02-01 15:26:41 回复(0)

C++

牛客858408745号

vector<int> reOrderArrayTwo(vector<int>& array) {
// write code here
int len = array.size(), temp;
int i, j = len-1;
for(i = 0; i < j; ){
if(array[i] % 2 != 0) i++;
else{
while(array[j] % 2 == 0) j--;
if(i < j){
temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}

发表于 2021-11-07 21:51:15 回复(0)

Python 3

牛客736356489号

from typing import List
class Solution:
    def reOrderArrayTwo(self , array: List[int]) -> List[int]:
        # write code here
        idx=1
        n=len(array)
        l=0
        while l < n-idx:
            if array[l]&1:
                l+=1
            else:
                array[l],array[-idx]=array[-idx],array[l] # 偶数换到队尾
                idx+=1
        return array

发表于 2021-10-16 21:10:15 回复(0)

C++

猪奔

        int i = 0, j = arr.size() - 1;
        while(i < j){
            if(arr[i]%2 == 1 && arr[j]%2 == 0) i++,j--;
            else if(arr[i]%2 == 1 && arr[j]%2 == 1) i++;
            else if(arr[i]%2 == 0 && arr[j]%2 == 1) swap(arr[i++],arr[j--]);
            else j--;
        }
        return arr;
    }
};

发表于 2021-10-14 19:49:22 回复(0)

牛客570525777号

这题双指针应该也可以但是没这个方法简洁同是o(n) 你却更秀

发表于 2021-10-17 08:56:50 回复(0)

Java

该去学习了

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] reOrderArrayTwo (int[] array) {
        if(array.length==0||array.length==1){
            return array;
        }
        int left=0;
        int right=array.length-1;
        while(left<right){
            if(array[left]%2==0&&array[right]%2!=0){
                int temp=array[left];
                array[left]=array[right];
                array[right]=temp;
                left++;
                right--;
            }
            if(array[left]%2!=0){
                left++;
            }
            if(array[right]%2==0){
                right--;
            }
        }
        return array;
    }
}

发表于 2021-10-14 20:33:17 回复(0)

Java

牛客715859853号

public int[] reOrderArrayTwo (int[] array) {
        // write code here
        for(int i = 0, j = 0; i < array.length; i++) {
            if(array[i] % 2 != 0) {
                int temp = array[i];
                array[i] = array[j];
                array[j++] = temp;
            }
        }
        return array;
    }

发表于 2021-11-19 01:36:15 回复(3)

Python 3

H-n

单纯使用自带排序解决问题。。。第一次使用自带学习一下

class Solution:
    def reOrderArrayTwo(self , array: List[int]) -> List[int]:
        # write code here
        array.sort(key=self.rule)
        return array
    def rule(self,m):
        if  m % 2 == 0:
            return 1
        else:
            return 0

发表于 2021-10-17 12:06:41 回复(0)

Java

牛客208400313号

双指针法

public int[] reOrderArrayTwo(int[] array) {
        int l = 0, r = array.length - 1, tmp = 0;

        // 终止条件：左右指针相遇
        while (l < r) {
            if ((array[l] & 1) == 1) {
                // 奇数：左指针往右挪
                l++;
            } else {
                // 偶数：交换后，右指针往左挪
                tmp = array[l];
                array[l] = array[r];
                array[r] = tmp;
                r--;
            }
        }
        return array;
    }

发表于 2022-08-16 20:24:49 回复(0)

C++

Noah.Suming

class Solution {
public:
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int l = -1, r = array.size();
        if (r == 0) return array;
        while (l < r) {
            while(array[++l] % 2 == 1);
            while(array[--r] % 2 == 0) ;
            if (l < r) swap(array[l], array[r]);
        }
        return array;
    }
};

类似于快排思想

发表于 2022-02-01 12:01:09 回复(0)

C++

Spectre_

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        // 时间复杂度O(N)，空间复杂度O(1)
        int left = 0, right = array.size() - 1;
        while (left < right) {
            while (array[left] % 2) ++left;
            if (left >= right) break;
            while (array[right] % 2 == 0) --right;
            if (left >= right) break;
            swap(array[left++], array[right--]);
        }
        return array;
    }
};

发表于 2022-11-18 23:46:17 回复(0)

Python3

牛客592571751号

class Solution:
    def reOrderArrayTwo(self , array: List[int]) -> List[int]:
        # write code here
        n = len(array)
        i=0
        while i<n:
            if array[i]%2==0:
                array.append(array[i])
                array.pop(i)
                n -=1
            else:
                i +=1
        return array

发表于 2022-04-21 16:20:53 回复(1)

C++

JerryGuCN

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

编辑于 2024-03-13 22:59:57 回复(0)

yzc885530

[1,3,4,2] 为什么不是正确结果？？？

编辑于 2024-03-13 20:18:38 回复(0)

Java

牛客276339250号

利用list的有序性，分别把奇数和偶数放在两个list中，然后合并两个list，在通过stream流把list转为int数组

import java.util.*;

public class Solution {

/**

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

* @param array int整型一维数组

* @return int整型一维数组

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

// write code here

List<Integer> list1=new ArrayList<>();

List<Integer> list2=new ArrayList<>();

for(int a:array){

if(a%2!=0){

list1.add(a);

}else{

list2.add(a);

}

list1.addAll(list2);

return list1.stream().mapToInt(Integer::intValue).toArray();

}

发表于 2023-11-22 17:40:11 回复(0)

Python 3

积极的小辣鸡想交流

class Solution:

def reOrderArrayTwo(self, array: List[int]) -> List[int]:

# write code here

myarray = []

for i in array:

if i % 2 == 1:

myarray.append(i)

for i in array:

if i % 2 == 0:

myarray.append(i)

return myarray

发表于 2023-10-20 20:34:28 回复(0)

C++

cua-cua-cua

//空间复杂度O(n)

// if(array.size() == 0 || array.size() == 1) return array;

// vector<int> res(array.size(), 0);

// int x = 0, y = 0;

// for(int i = 0;i < array.size();i++){

// if(array[i] % 2 == 1) y++;

// }

// for(int i = 0;i < array.size();i++){

// if(array[i] % 2 == 1){

// res[x] = array[i];

// x++;

// }

// else{

// res[y] = array[i];

// y++;

// }

// return res;

//空间复杂度O(1)

if(array.size() == 0 || array.size() == 1) return array;

int x = 0, y = array.size() - 1;

while(x < y){

if(array[x] % 2 == 0 && array[y] % 2 == 1)

swap(array[x], array[y]);

if(array[x] % 2 == 1)

x++;

if(array[y] % 2 == 0)

y--;

}

return array;

}

发表于 2023-10-09 23:06:47 回复(0)

林祥和

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        // write code here
        int size = array.size();
        vector<int> odd;
        vector<int> even;
        vector<int> res;
        for(int i = 0; i < size; i++){
            if(array[i] % 2 == 1)
                odd.push_back(array[i]);
            else
                even.push_back(array[i]);
        }
        res.insert(res.begin(), odd.begin(), odd.end());
        res.insert(res.end(), even.begin(), even.end());
        return res;
    }
};

发表于 2023-09-11 16:22:19 回复(0)

提交观点

问题信息

数组排序

上传者：牛客301499号

难度：

78条回答 110收藏 4051浏览

通过挑战的用户

查看代码

夜雨笙歌

2022-09-16 11:12:42
我就是不明白_

2022-09-16 10:07:00
牛客38330...

2022-09-15 21:22:37
想run的打工...

2022-09-15 20:23:56
芝士挞

2022-09-15 19:33:09

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

输入

输出

说明

输入

输出

说明

输入

输出

双指针法

问题信息

热门推荐

通过挑战的用户

相关试题