189. 轮转数组

新建数组

• 新建一个一样长度的数组，数组长度 len，原数组索引 i，映射至新数组索引"(i+k)%len"
• 时间复杂度 O(n)，空间复杂度 O(n)

连接数组

• 复制一遍放在原数组后面
• 从 (len - k) 处取 len 长数组

原位替换

• 数组长度 len，k%len 得到偏移量 n

• 将位置 i 放到位置 (i+n)%len，i=(i+n)%len，循环

• 若 i 变为初始 i，则 i+1 重复，若 i < n，则重复出现 n 次后结束

• 时间复杂度 O(n)，空间复杂度 O(1)

  void rotate(vector<int>& nums, int k) {
      k = k % nums.size();
      int count = 0;
      int i = 0;
      int originI = 0;
      int nextI = nums.size();
      int nextValue = nums[i];
      int curValue = 0;
      while (count < k)
      {
          curValue = nextValue;
          nextI = (i+k)%nums.size();
          nextValue = nums[nextI];
          nums[nextI] = curValue;
          if (nextI == originI && count < k - 1)
          {
              originI = ++nextI;
              nextValue = nums[nextI];
          }
          i = nextI;
          if (i < k)
          {
              count++;
          }
      }
  }

  38/38 cases passed (24 ms)
  Your runtime beats 75.42 % of cpp submissions
  Your memory usage beats 45.24 % of cpp submissions (24.8 MB)