【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

本问题对应课程链接：剑指offer刷题第六期

要求：

1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 79 15

共以下 15 个回答

mpweixin用户普通 2024年4月2日下午4:14

public int[] trainingPlan(int[] actions) {
int n=actions.length;
int i=0,j=n-1;
while(i<j){
while(i<j&&actions[i]%21){
i++;
}
while(i<j&&actions[j]%20){
j–;
}
if(actions[i]%20&&actions[j]%21&& i<j){
int t=actions[i];
actions[i]=actions[j];
actions[j]=t;
}
i++;j–;
}
return actions;
}
思路：双指针交换

0 赞同 0 条回复

登录以回复
神经蛙普通 2024年3月28日上午12:14

class Solution {
public:
vector trainingPlan(vector& actions) {
int i = 0; int j = actions.size() – 1;
while(i < j)
{
while(i<j && (actions[i] & 1) 1) i++;
while(i<j && (actions[j] & 1) 0) j–;
swap(actions[i], actions[j]);
}
return actions;
}
};
时间复杂度O（n）空间复杂度O(1)

0 赞同 0 条回复

登录以回复
扣子普通 2024年3月27日下午9:49

java
class Solution{
public int[] trainingPlan(int[] actions){
int i = 0, j = actions.length – 1, tmp;
while(i < j){
while(i < j && (actions[i] & 1) 1) i++;
while(i < j && (actions[j] & 1) 0) j–;
tmp = actions[i];
actions[i] = actions[j];
actions[j] = tmp;
}
return actions;
}
}
提交

0 赞同 0 条回复

登录以回复

言之命至普通 2024年3月27日下午8:56

class Solution {
    public int[] exchange(int[] nums) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        int left = 0;
        int right = nums.length - 1;
        while(left < right){
            while(left < right && nums[left] % 2 != 0) left++; //不是偶数，就向右走
            while(left < right && nums[right] % 2 != 1) right--;//不是奇数，就向做左走

            int temp = nums[left];//交换
            nums[left] = nums[right];
            nums[right] = temp;
        }

        return nums;
    }
}

时间复杂度：O(n)
额外空间复杂度：O(1)

0 赞同 0 条回复

Jimmy 普通 2024年3月26日下午7:25

双指针，左面的指针找到第一个偶数，右面的指针找到第一个奇数，然后两者互换

class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        if(actions.empty())return actions;
        int left = 0;
        int right = actions.size()-1;
        while(left < right)
        {
            while(left < right && (actions[left] & 1) == 1)
            {
                left++;
            }
            while(left < right && (actions[right] & 1) == 0)
            {
                right--;
            }
            swap(actions[left],actions[right]);
        }
        return actions;
    }
};

0 赞同 0 条回复

紫芝普通 2024年3月26日下午6:27

时间复杂度：O(n)
空间复杂度：O(1)

func trainingPlan(actions []int) []int {
    start, end := 0, len(actions)-1
    for start < end {
        if (actions[start] & 1) == 1 { start++ 
        } else if (actions[end] & 1) == 0 { end-- 
        } else {
            actions[start], actions[end] = actions[end], actions[start]
            start++
            end--
        }
    }
    return actions
}

0 赞同 0 条回复

heathhou 普通 2024年3月26日下午12:00

class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        if(actions.empty()){
            return actions;
        }
        int left = 0;
        int right = actions.size() - 1;
        while(left < right){
            while(left < right && actions[left] % 2 == 1)
                left++;
            while(left < right && actions[right] % 2 == 0)
                right--;

            int temp = actions[left];
            actions[left] = actions[right];
            actions[right] = temp;
        }
        return actions;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

一个达不刘普通 2024年3月26日上午10:02

class Solution {
public:
vector trainingPlan(vector& actions) {
int n = actions.size();
vector arr;
for(auto act:actions){//找奇数
if(act%21){
arr.push_back(act);
}
}
for(auto act:actions){//找偶数
if(act%20){
arr.push_back(act);
}
}
return arr;
}
};

0 赞同 0 条回复

登录以回复
Yox 普通 2024年3月26日上午1:22

class Solution:
def trainingPlan(self, actions: List[int]) -> List[int]:
if not actions: return []
left,right = 0,len(actions)-1
while left<right :
while left<right and actions[left]%2 != 0: left += 1
while left<right and actions[right]%2 0:right -= 1
actions[left],actions[right] = actions[right],actions[left]
return actions
时间 n 空间 1

0 赞同 0 条回复

登录以回复

白雪公主倒拔垂杨柳永久会员 2024年3月25日下午11:48

class Solution {
    public int[] trainingPlan(int[] actions) {
        int left =0;
        int right = actions.length-1;

        while(left<right){
            while(right >left && actions[right]%2==0)  right--;
            while(left < right && actions[left]%2==1) left++;
            int temp = actions[right];
            actions[right]=actions[left];
            actions[left]=temp;
        }

        return actions;
    }
}

时间复杂度：O(n)
额外空间复杂度：O(1)

0 赞同 0 条回复

Raphtalia. 普通 2024年3月25日下午11:45

class Solution {
public:
vector trainingPlan(vector& actions) {
int l = 0, r = actions.size() – 1;
while(l < r) {
//l指偶数，r指奇数
while(actions[r] % 2 0 && l < r) {
r –;
}
while(actions[l] % 2 1 && l < r) {
l ++;
}
swap(actions[l],actions[r]);
}
return actions;
}
};时间复杂度O（n)，空间复杂度O（1）

0 赞同 0 条回复

登录以回复
云无深雁影普通 2024年3月25日下午11:09

class Solution {
public int[] trainingPlan(int[] actions) {
int oddPtr = -1;
int evenPtr = -1;
while(oddPtr < actions.length && evenPtr < actions.length){
oddPtr++;
evenPtr++;
while(evenPtr < actions.length && actions[evenPtr] % 2 1)
evenPtr++;
oddPtr = Math.max(evenPtr, oddPtr);
while(oddPtr < actions.length && actions[oddPtr] % 2 0)
oddPtr++;
if(oddPtr >= actions.length || evenPtr >= actions.length)
break;
int temp = actions[oddPtr];
actions[oddPtr] = actions[evenPtr];
actions[evenPtr] = temp;
}
return actions;
}
}//时间复杂度On
//空间复杂度O1

0 赞同 0 条回复

登录以回复
机电皮怪永久会员 2024年3月25日下午9:04

时间复杂度O(N),空间复杂度O(1)
不知道为什么循环里面用if移动指针会出错

“`C++
class Solution {
public:
vector trainingPlan(vector& actions) {
if(actions.empty() == true)
{
return {};
}
//双指针
int left = 0, right = actions.size() – 1;
while(left < right) { while(actions[left] % 2 == 1 && left < right) { left++; } while(actions[right] % 2 == 0 && left < right ) { right--; } //前面的偶数和后面的奇数交换 int temp = actions[right]; actions[right] = actions[left]; actions[left] = temp; } return actions; } }; ···

0 赞同 0 条回复

登录以回复

王位詮釋普通 2024年3月25日下午8:21

class Solution {
    public int[] trainingPlan(int[] actions) {
        if(actions==null||actions.length==0){
            return actions;
        }
        int l = 0;
        int r = actions.length-1;
        while(l<r){
            while(l<r&&actions[l]%2!=0){
                l++;
            }
            while(l<r&&actions[r]%2==0){
                r--;
            }
            int temp = actions[l];
            actions[l] = actions[r];
            actions[r] = temp;
        }
        return actions;
    }
}
思路：类似于快排，使用左右指针，l为左指针，r为右指针，如果l所指的元素是奇数，那就一直往后移动，否则转向r，r也是一样，如果所指元素一直为偶数，那就不变，否则将l和r所指元素交换。
时间复杂度：O(nlogn)，空间复杂度：O(1)

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月25日下午7:44

打卡

class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int n = actions.size();
        int i = 0, j = n - 1;
        while(i < j) {
            while(i < j && actions[i] % 2 == 1) i++;
            while(i < j && actions[j] % 2 == 0) j--;
            swap(actions[i], actions[j]); 
        }
        return actions;
    }
};

0 赞同 0 条回复

# 回答此问题取消回复

后才能回答

【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

共以下 15 个回答

# 回答此问题 取消回复

# 回答此问题取消回复