【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面

简介: 【一刷《剑指Offer》】面试题 14:调整数组顺序使奇数位于偶数前面

力扣对应题目链接:LCR 139. 训练计划 I - 力扣(LeetCode)

牛客对应题目链接:调整数组顺序使奇数位于偶数前面(二)_牛客题霸_牛客网 (nowcoder.com)

核心考点:数组操作,排序思想的扩展使用。


一、《剑指Offer》对应内容


二、分析题目

按照题目意思,其实跟快排的思路一致,我们只需要定义双指针 left 和 right 分别指向数组的第一个元素和最后一个元素,接着让 left 往后遍历,直到找到前半部分的第一个偶数,让 right 向前遍历,直到找到后半部分的第一个奇数,然后交换 left 和 right 所在位置的数即可,遍历后的数组就是我们要的答案。


扩展:假设现在新增需求,需要保证奇数和奇数,偶数和偶数之间的相对位置不变。

解决这个问题的方法也比较多,这里我们采用较优方式解决一下,借鉴插入排序的思想。做法:从左向右遍历,每次遇到的都是最前面的奇数,将该奇数之前的内容(偶数序列)整体后移一个位置,腾出位置后,将奇数保存在它将来该在的位置,因为我们是从左往右放的,没有跨越奇数,所以一定是相对位置不变的


三、代码(C++)

1、方法一(头尾双指针法)

//写法一
class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int n=actions.size();
        int left=0, right=n-1;
        while(left<right)
        {
            while(left<right && actions[left]%2==1)
                left++;
            while(left<right && actions[right]%2==0)
                right--;
            if(left<right)
                swap(actions[left], actions[right]);
        }
        return actions;
    }
};
 
//写法二
class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int n=actions.size();
        int left=0, right=n-1;
        while(left<right)
        {
            while(left<right && (actions[left]&1))
                left++;
            while(left<right && !(actions[right]&1))
                right--;
            if(left<right)
                swap(actions[left], actions[right]);
        }
        return actions;
    }
};
//牛客网
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param array int整型vector 
     * @return int整型vector
     */
    vector<int> reOrderArrayTwo(vector<int>& array) {
        int n=array.size();
        int left=0, right=n-1;
        while(left<right)
        {
            while(left<right && array[left]%2==1)
                left++;
            while(left<right && array[right]%2==0)
                right--;
            if(left<right)
                swap(array[left], array[right]);
        }
        return array;
    }
};

2、方法二(插入法-保证相对顺序不变)

class Solution {
public:
    vector<int> trainingPlan(vector<int>& actions) {
        int n=actions.size();
        int k=0; //记录已排好序的奇数个数
        for(int i=0; i<n; i++)
        {
            if(actions[i]%2==1)
            {
                int tmp=actions[i]; //先将当前奇数保存起来
                int j=i;
                while(j>k)
                {
                    actions[j]=actions[j-1];
                    j--;
                }
                actions[k++]=tmp; //将奇数保存在它将来该在的位置
            }
        }
        return actions;
    }
};


相关文章
|
5天前
|
存储 算法
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
经典的滑动窗口的题目 力扣 2799. 统计完全子数组的数目(面试题)
|
18天前
|
开发框架 .NET
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
技术好文共享:面试题:找出数组中只出现一次的2个数(异或的巧妙应用)(出现3次)
|
1月前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
2月前
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
【一刷《剑指Offer》】面试题 23:从上往下打印二叉树
|
2月前
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
【一刷《剑指Offer》】面试题 22:栈的压入、弹出系列
|
2月前
|
算法
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
【一刷《剑指Offer》】面试题 21:包含 main 函数的栈
|
2月前
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
【一刷《剑指Offer》】面试题 20:顺时针打印矩阵
|
2月前
【一刷《剑指Offer》】面试题 19:二叉树的镜像
【一刷《剑指Offer》】面试题 19:二叉树的镜像
|
2月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
2月前
【一刷《剑指Offer》】面试题 17:合并两个排序的链表
【一刷《剑指Offer》】面试题 17:合并两个排序的链表