189.轮转数组

发表于： 分类于：
字数： 454 阅读：≈ 1分钟

🔄 189.轮转数组

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

提示：

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

思路

基本思想

考研408的题目，直接将数组逆序三遍即可，但是需要注意k>nums.size()的情况，k==nums.size()相当于走了一圈回到自身，没有任何变化，所以逆序之前需要做一件事，对k进行预处理，处理方式为： $$ k=k>nums.size()?(k%nums.size()):k $$ 而不是： $$ k=k>nums.size()?(k-nums.size()):k; $$ 因为k有可能比两个nums.size()还要大，其余的没有要注意的地方

执行流程

  1. 编写逆序函数
  2. 预处理k
  3. 执行三遍逆序

代码

根据以上分析，得出以下代码:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    //将元素三次逆序即可
    void rotate(vector<int>& nums, int k) {
        //因为k大于nums.size时，相当于走了一圈回到原地，做了无用功
        //只有不回到原地的操作才是正确的
        k=k>nums.size()?k%nums.size():k;
        reverse(nums,0,nums.size()-k);
        reverse(nums,nums.size()-k,nums.size());
        reverse(nums,0,nums.size());
    }
    //传递的是引用才能将形参的改变传递给实参
    void reverse(vector<int> &nums,int start,int end){
        for(int i=start,j=end-1;i<j;++i,--j){
            int temp=nums[i];
            nums[i]=nums[j];
            nums[j]=temp;
        }
    }
};

总结

注意逆序之前k需要预处理，因为有可能k>nums.size()

并且逆序时需要传递引用，否则逆序之后的结果无法保存