【排序算法运用】剑指 Offer 21. 调整数组顺序使奇数位于偶数前面-跟着帅地玩副业，开拓第二曲线PlayOffer

lQl 永久会员 2024年12月22日下午6:57

双指针
时间复杂度O(n)
空间复杂度O(1)

class Solution {
    public int[] trainingPlan(int[] actions) {
        int n = actions.length;
        int l = 0;
        int r = n - 1;
        while (l < r) {
            if (actions[l] % 2 == 0) {
                if (actions[r] % 2 != 0) {
                    int tmp = actions[l];
                    actions[l] = actions[r];
                    actions[r] = tmp;
                } else {
                    r--;
                }
            } else {
                l++;
            }
        }
        return actions;
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月21日下午10:02

class Solution {
    public int[] trainingPlan(int[] actions) {
        if(actions.length<=1) return actions;
        int left=0;
        int right=actions.length-1;
        int tmp;
        while(left<right){
            while(left<right&&(actions[left]&1)==1) left++;
            while(left<right&&(actions[right]&1)==0) right--;
            tmp=actions[right];
            actions[right]=actions[left];
            actions[left]=tmp;
        }
        return actions;
    }
}
时间复杂度：O（n）
空间复杂度：O（1）

0 赞同 0 条回复

陆狗陆狗普通 2024年12月19日上午1:14

解题思路
– 在数组的两端，左右指针，左边找到第一个偶数后停止，右边找到第一个奇数后停止，进行交换
【题解1】自己的解法，利用的是外面的while循环，去找到左边找到第一个偶数后停止，右边找到第一个奇数后停止

class Solution {
    public int[] trainingPlan(int[] actions) {
        // 首位双指针，找到后等待
        // 边界值判断
        if (actions.length <= 1) {
            return actions;
        }
        // 左右指针，左边找到第一个偶数后停止，右边找到第一个奇数后停止，进行交换
        int left = 0;
        int right = actions.length - 1;
        boolean flagLeft = false;
        boolean flageRight = false;
        while (left < right) {
            // 找到后进行标记
            // 【错误点】位运算要加括号，否则要报错
            if ((actions[left] & 1) == 0) {
                flagLeft = true;
            } else {
                left++;
            }
            if ((actions[right] & 1) == 1) {
                flageRight = true;
            } else {
                right--;
            }
            // 都标记为true时，需要进行交换
            if (flagLeft && flageRight) {
                // 交换
                swap(actions, left, right);
                // 复原标识
                flagLeft = false;
                flageRight = false;
            }
        }
        return actions;
    }

    private void swap(int[] actions, int indexa, int indexb) {
        int tmpt = actions[indexa];
        actions[indexa] = actions[indexb];
        actions[indexb] = tmpt;

    }
}

错误点1：位运算要加括号，否则要报错

【题解2】利用内部while，去实现找到第一个的效果，比外部统一循环要快一点

class Solution {
    public int[] trainingPlan(int[] actions) {
        // 首位双指针，找到后等待
        // 边界值判断
        if (actions.length <= 1) {
            return actions;
        }
        // 左右指针，左边找到第一个偶数后停止，右边找到第一个奇数后停止，进行交换
        int left = 0;
        int right = actions.length - 1;
        while (left < right) {
            // 左边找到第一个偶数后停止
            while (left < right && (actions[left] & 1) == 1) {
                left++;
            }
            // 右边找到第一个奇数后停止
            while (left < right && (actions[right] & 1) == 0) {
                right--;
            }
            // 执行交换
            swap(actions, left, right);
        }
        return actions;
    }

    private void swap(int[] actions, int indexa, int indexb) {
        int tmpt = actions[indexa];
        actions[indexa] = actions[indexb];
        actions[indexb] = tmpt;

    }
}

0 赞同 0 条回复

秋山丽奈普通 2024年12月17日下午7:55

思路：使用快慢指针

class Solution {
    public int[] trainingPlan(int[] nums) {
        int slow = 0;
        int fast = 0;
        while(fast < nums.length){
            if((nums[fast]&1)==1) {
                swap(nums,slow,fast);
                slow ++;
            }
            fast++;
        }
        return nums;
    }

    public void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] =temp;
        return;
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月16日下午7:54

class Solution {
public int[] trainingPlan(int[] actions) {
int l = 0, r = actions.length-1;
while(l < r){
while(l < r && actions[l] % 2 1){
l++;
}
while(l < r && actions[r] % 2 0){
r–;
}
if(l < r){
int temp = actions[l];
actions[l] = actions[r];
actions[r] = temp;
}
}
return actions;
}
}
时间：O（n）
空间：O（1）

0 赞同 0 条回复

迢迢星野普通 2024年12月16日下午7:26

class Solution {
    /**
     * 教练使用整数数组 actions 记录一系列核心肌群训练项目编号。为增强训练趣味性，需要将所有奇数编号训练项目调整至偶数编号训练项目之前。
     * 请将调整后的训练项目编号以 数组 形式返回。
     * 
     * 题意解读：将所有奇数编号 调整至偶数编号之前
     * 方法一：奇数和偶数分别用两个 list 存储，再将偶数的 list 存入到奇数的 list 中即可
     * 方法二：双指针，一个维护奇数，一个维护偶数，进行元素交换即可
     * 
     * @param actions 训练项目编号数组
     * @return 调整后的训练项目编号数组
     */
    public int[] trainingPlan(int[] actions) {
        // 初始化快慢指针，fast 负责遍历数组，slow 负责记录奇数位置
        int fast = 0, slow = 0;
        // 遍历整个数组
        while (fast < actions.length) {
            // 当遇到奇数时，进行交换
            if (actions[fast] % 2 == 1) {
                int tmp = actions[fast];
                actions[fast] = actions[slow];
                actions[slow] = tmp;
                // slow 指针向前移动，准备记录下一个奇数位置
                slow++;
            }
            // fast 指针向前移动，继续遍历数组
            fast++;
        }
        // 返回调整后的数组
        return actions;
    }
}

思路：双指针
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

晓宇普通 2024年12月16日下午4:00

class Solution {
public:
    // 类快排思想
    vector<int> trainingPlan(vector<int>& actions) {
        if(actions.empty()) return vector<int> ();
        int lef = 0, rit = actions.size() - 1;
        while(lef < rit){
            while(lef < rit && actions[rit] % 2 == 0) rit -= 1;
            while(lef < rit && actions[lef] % 2 == 1) lef += 1;
            if(lef < rit) swap(actions,lef,rit); 
        }
        return actions;       
    }

    void swap(vector<int>& arr, int idx, int idy){
        __typeof(arr[idx]) __c = arr[idx];
        arr[idx] = arr[idy];
        arr[idy] = __c;
    }
};
// on o1

0 赞同 0 条回复

Aatorx 永久会员 2024年12月16日下午3:39

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

左指针找奇数，右指针找偶数，交换即可。
时间复杂度O(N)，空间复杂度O(1)。

0 赞同 0 条回复

月下足迹普通 2024年12月16日上午10:44

//方法1 ，创造奇偶数列表最后合并
public int[] trainingPlan(int[] actions) {
int n = actions.length;
List odds = new ArrayList<>();
List even = new ArrayList<>();

    for(int nums : actions) {
        if((nums & 0x01) == 1) {
            odds.add(nums);
        }else {
            even.add(nums);
        }
    }

    int [] result = new int[n];
    int index = 0;
    for(int i : odds) {
        result[index++] = i;
    }
    for(int j : even) {
        result[index++] = j;
    }

    return result;
}

//方法2双指针思路
public int[] trainingPlan(int[] actions) {
int n = actions.length;
int i = 0 , j = n – 1 , tmp;
while(i < j) {
//指针i向右遍历数组，j向左遍历
while(i < j && (actions[i] & 0x01) 1) i++;
while(i < j && (actions[j] & 0x01) 0) j–;
tmp = actions[i];
actions[i] = actions[j];
actions[j] = tmp;
}
return actions;
}

0 赞同 0 条回复

jaron 普通 2024年12月14日下午9:18

class Solution {
    public int[] trainingPlan(int[] actions) {
        if (actions == null || actions.length <= 1) {
            return actions;
        }
        int l = 0, r = actions.length - 1;
        while (l < r) {
            // 记得判断 l < r
            // 从左往右找到第一个偶数
            while (l < r && actions[l] % 2 == 1)
                l++;
            // 从右往左找到第一个奇数
            while (l < r && actions[r] % 2 == 0)
                r--;
            // 交换
            int temp = actions[l];
            actions[l] = actions[r];
            actions[r] = temp;
        }
        return actions;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月14日下午6:48

方法一

两个指针，一个在0 一个在最后，若左指针指向的为奇数，右移一格，右指针指的是偶数，左移一格，
其他情况全部交换左右指针对应的值，交换之后两个指针都要移动
最后left>right或者left=right结束循环
class Solution {
    public int[] trainingPlan(int[] actions) {
        int left=0,right=actions.length-1;
        while(left<right){
            if(actions[left]%2!=0){
                left++;
                continue;
            }
            if(actions[right]%2==0){
                right--;
                continue;
            }
         swap(actions,left,right);
         left++;
         right--;
        }
        return actions;
    }

    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

On O1

方法二

快排思想,一个慢指针标记奇数要存放的位置,一个快指针寻找奇数
class Solution {
    public int[] trainingPlan(int[] actions) {
        int slow=-1;
        int fast=0;
        while(fast!=actions.length){
            if(actions[fast]%2!=0){
                swap(actions,++slow,fast++);
            }
            else fast++;
        }
        return actions;
    }

    void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

On
O1

0 赞同 0 条回复

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

共以下 11 个回答

方法一

方法二

# 回答此问题取消回复

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

共以下 11 个回答

方法一

方法二

# 回答此问题 取消回复

# 回答此问题取消回复