当前位置 博文首页 > 中流击水，浪遏飞舟：一题多解与优化 && 剑指 Offer 21.

最大化 缩小

    中流击水，浪遏飞舟：一题多解与优化 && 剑指 Offer 21.

    作者：[db:作者] 时间：2021-08-26 12:47

    1. 原始写的菜鸡代码，冗长又多判断：

    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int F=0,R=0;
        int size=nums.size();
        while(R<size){      //防止最后的++后溢出
            while(F<size&&(nums[F]%2)){
                F++;
            }
            if(R<=F){
                R=F+1;
            }
            while(R<size&&!(nums[R]%2)){
                R++;
            }
            if(F>=size||R>=size){    //加这个条件防止后面交换溢出
                break;
            }
            int temp=nums[R];
            nums[R]=nums[F];
            nums[F]=temp;
            F++,R++;
        }
        return nums;
    }
};

    2.看了别人的题解的收获进行修改：

    2.1 使用交换函数swap();头文件：#include< iostream >；

    int temp=nums[R];
nums[R]=nums[F];
nums[F]=temp;

    变成：

    swap(nums[F],nums[R]);

    2.2.上面的快慢指针冗余，本意是F指向偶数，R指向奇数，但使用了两重while()循环且里面有两个while()循环，增加了时间复杂度，然而一重while()就可以搞定，也可以将内层的两个循环改成if+continue判断；

    修改后的快慢指针解法如下：

    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int F=0,R=0;
        int size=nums.size();
        while(R<size){      //防止最后的++后溢出
            if(nums[R]%2){
                swap(nums[F],nums[R]);
                F++;
            }
            R++;
        }
        return nums;
    }
};

    2.3 快慢指针也可以命名为fast,low，左右指针也可命名left,right;

    2.4 判断奇数偶数除了"模2"外，还可以与1进行相与"&1"，注意：！和&优先级相同且从右到左结合，加括号。

    3. 还有首尾指针解法，不过这种方法可能使得原始数组的数字的相对顺序改变；

    class Solution {
public:
    vector<int> exchange(vector<int>& nums) {
        int F=0,R=nums.size()-1;
        while(F<R){
            if(nums[F]&1){
                F++;
                continue;
            }
            if(!(nums[R]&1)){
                R--;
            }
            swap(nums[F],nums[R]);
        }
        return nums;
    }
};

    4.除此之外，还可以用两个vector< int >数组（奇数一个数组，偶数一个数组），不过时间复杂度和空间复杂度较前面的O（n）时间复杂度大。

    cs
    上一篇：中流击水，浪遏飞舟：一题多解&&剑指 Offer 15. 二进制
    下一篇：没有了