LeetCode 面试经典 150_数组/字符串_轮转数组（6_189_C++_中等）（额外数组；转置）

题目描述：

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

输入输出样例：

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

示例 2：
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释：
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：
1 <= nums.length <= 10⁵
-2³¹ <= nums[i] <= 2³¹ - 1
0 <= k <= 10⁵

题解：

解题思路：

思路一（额外数组）：

1、我们可以采用额外的数组来暂时存储从后方移动向前方的k个元素，再将前方剩余的元素移动到后方，再将数组暂存的元素放入前方。

2、以nums = [1,2,3,4,5,6,7], k = 3为例
① k=3意味着末尾有三个元素移到前端，且三个元素相对位置不变。
② 我们可以使用一个额外的空间tmp存储末尾移动到前端的元素tmp=[5,6,7]。
③ 则此时nums中的元素可以进行移动nums=[1,2,3,1,2,3,4]。
④ 最后我们将tmp中的元素放在nums的前端 nums=[5,6,7,1,2,3,4]

3、复杂度分析：
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。
② 空间复杂度：O(N)，取决于k%nums.size()的大小，取值0~N-1，所以为O(N)。

思路二（转置）：

1、先将数组进行翻转，再将两个分数组进行翻转。
例：nums = [1,2,3,4,5,6,7], k = 3。
① 先将nums翻转[7,6,5,4,3,2,1]
②再将前k=3个元素翻转，后续元素也翻转[5,6,7,1,2,3,4] 。

2、复杂度分析
① 时间复杂度：O(N)，其中 N 是数组中的元素数量。因翻转数组两次。
② 空间复杂度：O(1)，我们只需要常数空间存放若干变量。

代码实现

代码实现（思路一（额外数组））：

class Solution1 {
public:void rotate(vector<int>& nums, int k) {// 如果旋转步数k与数组长度相同，则不需要进行任何操作if (nums.size() == k){return ;}// 如果k大于数组长度，将k缩小为k % nums.size()，因为旋转k次和旋转k % nums.size()次效果相同else if(k > nums.size()){k = k % nums.size();}// 创建一个临时数组，用于保存旋转后末尾的部分vector<int> tmp;// 将数组的后k个元素存入临时数组tmpfor (int i = nums.size() - k; i < nums.size(); i++){tmp.push_back(nums[i]);}// 将数组的前n-k个元素（即从0到nums.size()-k-1的位置）往后移动k位for (int j = nums.size() - k - 1; j >= 0 ; j--){nums[j + k] = nums[j];}// 将临时数组tmp的前k个元素放回数组的前面for (int n = 0; n < k; n++){nums[n] = tmp[n];}}
};

代码实现（思路二（转置））：

class Solution2 {
private:// 反转数组的辅助函数void reverse(vector<int>& nums, int left, int right){int tmp;// 通过交换元素来反转数组的指定部分while (left < right){tmp = nums[left];          // 临时保存左边的元素nums[left] = nums[right];  // 将右边的元素放到左边nums[right] = tmp;         // 将临时保存的左边元素放到右边left++;                    // 左指针向右移动right--;                   // 右指针向左移动}}public:void rotate(vector<int>& nums, int k) {// 如果数组的大小与旋转次数k相等，直接返回，因为旋转后数组不会变化if (nums.size() == k){return ;}// 如果k大于数组的大小，减少不必要的旋转else if (k > nums.size()){k = k % nums.size();}// 步骤1: 反转整个数组reverse(nums, 0, nums.size() - 1);// 步骤2: 反转数组的前k个元素reverse(nums, 0, k - 1);// 步骤3: 反转数组的剩余部分reverse(nums, k, nums.size() - 1);}
};

以思路二为例进行调试

#include<iostream>
#include<vector>
using namespace std;class Solution2 {
private:// 反转数组的辅助函数void reverse(vector<int>& nums, int left, int right){int tmp;// 通过交换元素来反转数组的指定部分while (left < right){tmp = nums[left];          // 临时保存左边的元素nums[left] = nums[right];  // 将右边的元素放到左边nums[right] = tmp;         // 将临时保存的左边元素放到右边left++;                    // 左指针向右移动right--;                   // 右指针向左移动}}public:void rotate(vector<int>& nums, int k) {// 如果数组的大小与旋转次数k相等，直接返回，因为旋转后数组不会变化if (nums.size() == k){return ;}// 如果k大于数组的大小，减少不必要的旋转else if (k > nums.size()){k = k % nums.size();}// 步骤1: 反转整个数组reverse(nums, 0, nums.size() - 1);// 步骤2: 反转数组的前k个元素reverse(nums, 0, k - 1);// 步骤3: 反转数组的剩余部分reverse(nums, k, nums.size() - 1);}
};int main(int argc, char const *argv[])
{vector<int> nums={1,2,3,4,5,6,7};int k=3;Solution2 s;s.rotate(nums,k);for(auto const &i:nums){cout<<i<<" ";}return 0;
}

LeetCode 面试经典 150_数组/字符串_轮转数组（6_189)原题链接
欢迎大家和我沟通交流(✿◠‿◠)