​LeetCode刷题实战189:旋转数组

程序IT圈

共 1592字,需浏览 4分钟

 ·

2021-02-20 14:06

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 旋转数组,我们先来看题面:
https://leetcode-cn.com/problems/rotate-array/

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?


题意



给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
进阶:
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗?

示例


示例 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;i            record[(i+k)%nums.size()]=nums[i];
        nums.swap(record);
    }
    
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-180题汇总,希望对你有点帮助!
LeetCode刷题实战181:超过经理收入的员工
LeetCode刷题实战182:查找重复的电子邮箱
LeetCode刷题实战183:从不订购的客户
LeetCode刷题实战184:部门工资最高的员工
LeetCode刷题实战185:部门工资前三高的所有员工
LeetCode刷题实战186:翻转字符串里的单词 II
LeetCode刷题实战187:重复的DNA序列
LeetCode刷题实战188:买卖股票的最佳时机 IV

浏览 23
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报