题解 | #旋转数组#复习一下辗转相除法 讨论一下效率

旋转数组

https://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042

主要是辗转相除法求最大公约数还给小学老师了,复习一下

 class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型vector 给定数组
     * @return int整型vector
     */
    int gcd(int a,int b){
        //最大公约数,辗转相除法
        int t;
        while(b){
            t=b;
            b=a%b;
            a=t;
        }
        return a;
    }
    vector<int> solve(int n, int m, vector<int>& a) {
        // write code here
        if(!a.size()||a.size()==1)return a;
        //i代表每次挪动元素数量,j代表总的挪动次数
        int i,j,perRollSwaps,rollSize,curOffset,target,temp;
        rollSize=gcd(m,a.size());
        perRollSwaps=a.size()/rollSize;
        for(i=0;i<rollSize;++i){
            curOffset=i,
            temp=a[i];
            for(j=0;j<perRollSwaps;++j){
                target=(curOffset+m)%n;
                swap(temp,a[target]);
                curOffset=target;
            }
        }
        return a;
    }
};

看起来只执行了n次交换,但是!!但是!!

实际上这样并不比通用题解里翻转三次的做法快,尽管它看起来进行了2n次交换

因为mod运算(%)实际上是非常耗费性能的,甚至需要几十个机器周期!!!所以这样看似减少了赋值操作次数,却付出了一次取模运算的代价,得不偿失

白忙活一场,但是至少复习了下小学数学qwq

全部评论

相关推荐

机械打工仔:不管啥专业,找工作改简历的第一课先把你那排版改了,简历上不要写个人简历四个字,找你要简历的谁不知道这个是简历?而且还占那么多空间,直接把自己名字和基础信息写上面,整体字体大一些。 还有这种经典两页简历一页大空白,导出PDF的时候多了一页几乎全是白的你自己看着不难受吗随手的事为啥不能改掉呢,这是态度问题,你试想一下你是HR你打开简历看到格式都没调整过会是什么感受?你自己都不重视你的简历,HR更不会在意。 然后内容你那个做两年咖啡就别往里写了,简历在精不在多,你在往你的简历里打字的时候就要想好这东西对你要找的工作有没有帮助。自我评价写一行就行了,不如给专业技能单开一栏。核心课程均分90这个真别写了,把你上过的有用的专业课列出来也行。有很多地方废话很多的精炼一下,比如你校内项目第一个写的那些,全然没有重点。 好好修改一下,我看你内容也挺优秀的,别被一个随便做的简历耽误了,我一个同专业的打工人看了都揪心更别说一天看几百份简历的HR
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务