leetcode：189. 轮转数组

题目

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

示例：

  1. 输入: nums = [1,2,3,4,5,6,7], k = 3
  2. 输出: [5,6,7,1,2,3,4]
  3. 解释:
  4. 向右轮转 1 步: [7,1,2,3,4,5,6]
  5. 向右轮转 2 步: [6,7,1,2,3,4,5]
  6. 向右轮转 3 步: [5,6,7,1,2,3,4]
  1. 输入：nums = [-1,-100,3,99], k = 2
  2. 输出：[3,99,-1,-100]
  3. 解释: 
  4. 向右轮转 1 步: [99,-1,-100,3]
  5. 向右轮转 2 步: [3,99,-1,-100]

解答 & 代码

三次翻转：设数组 nums 向右轮转 k 个位置（注：k 要先对数组长度 len 取余）

  1. 翻转前 len - k 个数 nums[0, ..., len-k-1]
  2. 翻转后 k 个数 nums[len-k, ..., len-1]
  3. 翻转整个数组

例：nums = [1,2,3,4,5,6,7], k = 3

  1. 翻转前 len - k 个数：nums = [**4,3,2,1**,5,6,7]
  2. 翻转后 k 个数：nums = [4,3,2,1,**7,6,5**]
  3. 翻转整个数组：nums = [**5,6,7,1,2,3,4**]
  1. class Solution {
  2. public:
  3.     void rotate(vector<int>& nums, int k) {
  4.         int len = nums.size();
  5.         if(k >= len)        // 注意：如果 k >= len，则先取余
  6.             k = k % len;
  7.         // 三次翻转
  8.         reverse(nums.begin(), nums.begin() + len - k);    // 翻转前 len - k 个数
  9.         reverse(nums.begin() + len - k, nums.end());    // 翻转后 k 个数
  10.         reverse(nums.begin(), nums.end());                // 反转整个数组
  11.     }
  12. };

复杂度分析：设数组长为 N

  • 时间复杂度 O(N)：
  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：12 ms, 在所有 C++ 提交中击败了 99.85% 的用户
  4. 内存消耗：24.4 MB, 在所有 C++ 提交中击败了 62.29% 的用户