LeetCode刷题实战189:旋转数组
共 1592字,需浏览 4分钟
·
2021-02-20 14:06
Given an array, rotate the array to the right by k steps, where k is non-negative.
Follow up:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?
题意
示例
示例 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]
解题:3种解法,见下图代码注释。
class Solution {
public:
//解法1:翻转,时间复杂度为O(n),空间复杂度为O(1)
void rotate_1(vector<int>& nums, int k) {
k%=nums.size();
reverse(nums.begin(),nums.end());//反转整个字符串
reverse(nums.begin(),nums.begin()+k);//前k个字符反转
reverse(nums.begin()+k,nums.end());//后面的字符反转
}
//解法2:双重for,暴力数组旋转k次,时间复杂度为O(k*n),空间复杂度为O(1)
void rotate_2(vector<int>& nums, int k)
{
k%=nums.size();
int n=nums.size();
for(int i=0;i{
int temp=nums[n-1];//最后一个元素旋转到最前面
for(int j=n-1;j>0;--j)nums[j]=nums[j-1];
nums[0]=temp;//最后一个元素到底第一个元素的位置
}
}
//解法3:使用额外的数组,时间复杂度为O(n),空间复杂度为O(n)
void rotate_3(vector<int>& nums, int k)
{
vector<int> record(nums.size());
//将数组nums中的元素放到右移k个单位后的record数组
for(int i=0;irecord[(i+k)%nums.size()]=nums[i];
nums.swap(record);
}
};