BM97 旋转数组(描述一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M ＞=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …

66 阅读 0 评论 44 点赞

我是靠谱客的博主糟糕海燕，最近开发中收集的这篇文章主要介绍BM97 旋转数组(描述一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M ＞=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
        if(n<=1) return a;//当数组长度<=1，不管怎么移动都不变
        if(m%n==0) return a;//当移动n的倍数，相当于没移动
        int k=m%n;//计算需要右移的位数，因为可能m>n
        reverse(a.begin(),a.end());//整个反转
        reverse(a.begin(),a.begin()+k);//0~k位置反转
        reverse(a.begin()+k,a.end());//k~n位置反转
        return a;
    }
};

//模拟
class Solution {
public:
    vector<int> solve(int n, int m, vector<int>& a) {
       while(m--){
           a.insert(a.begin(),a.back());//从数组尾取出元素, 插入数组头
           a.pop_back();//删除数组尾的多余元素
       }
        return a;
    }
};