关关的刷题日记12——Leetcode 189. Rotate Array 方法1、2、3

关小刷刷题12 – Leetcode 189. Rotate Array 方法1、2、3

题目

Rotate an array of n elements to the right by k steps.For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

题目给出数组的长度和旋转次数,要求对整个数组向右进行旋转操作。

方法1

方法1:暴力求解,每次往右移动一步,时间复杂度为O(n2),超时了。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k=k%n;
        if(k==0)
            return;
        for(int i=0; i<k; i++)
        {
            int temp=nums[n-1];
            for(int j=n-1; j>0; j--)
            {
                nums[j]=nums[j-1];
            }
            nums[0]=temp;
        }
    }
};

方法2

方法2:额外开辟个数组,把旋转后得到的结果算出来一次性存到里面,然后再替换原来数组。时间复杂度O(n).

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k=k%n;
        if(k==0)
            return;
        vector<int>temp(n, 0);
        for(int i=0; i<n; i++)
        {
            temp[(i+k)%n]=nums[i];
        }
        for(int i=0; i<n; i++)
        {
            nums[i]=temp[i];
        }
    }
};

方法3

方法3:时间复杂度O(n),还不需要开辟额外空间,不过不容易想到,可以记下来这种方法。三次翻转法,第一次翻转全部,第二次翻转前k个,第三次翻转后n-k个。

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end)
    {
        for(int i=start; i<=(start+end)/2; i++)
        {
            int temp=nums[i];
            nums[i]=nums[start+end-i];
            nums[start+end-i]=temp;
        }
    }
    
    void rotate(vector<int>& nums, int k) {
        int n=nums.size(), temp=0;
        k=k%n;
        if(k==0)
            return;
        reverse(nums, 0, n-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, n-1);         
    }
};

方法4

方法4:师父出手,总能写出简洁优雅的代码。时间复杂度O(n).C++容器的insert()函数有以下三种用法: 最终*it=val;

//用法1:在指定位置it前“插入”值为val的元素,返回指向这个元素的迭代器, iterator insert( iterator it, const TYPE &val );

//用法2:在指定位置it前“插入”num个值为val的元素 void insert( iterator it, size_type num, const TYPE &val );

//用法3:在指定位置it前“插入”区间[start, end)的所有元素. void insert( iterator it, input_iterator start, input_iterator end );vector中插入一个元素时间复杂度是O(n), 批量插入的话时间复杂度也是O(n).

class Solution {
public:   
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k%=n;
        nums.insert(nums.begin(), nums.begin()+n-k, nums.end());
        nums.resize(n);
    }
};

聪明是需要积累的,加油!

以上就是关关关于这道题的总结经验,希望大家能够理解,有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390,也可以加入专知——Leetcode刷题交流群(请先加微信小助手weixinhao: Rancho_Fang)。

原文发布于微信公众号 - 专知(Quan_Zhuanzhi)

原文发表时间:2017-10-07

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏落影的专栏

程序员进阶之算法练习(三十五)LeetCode专场

LeetCode上的题目是大公司面试常见的算法题,今天的目标是拿下5道算法题: 题目1是基于链表的大数加法,既考察基本数据结构的了解,又考察在处理加法过程中的边...

48116
来自专栏Golang语言社区

深入解析快速排序算法的原理及其Go语言版实现

快速排序是一种基于分治技术的重要排序算法。不像归并排序是按照元素在数组中的位置对它们进行划分,快速排序按照元素的值对它们进行划分。具体来说,它对给定数组中的元素...

3375
来自专栏编程之旅

唠唠快速排序算法

每一个从事计算机相关方向工作的同学一定听说过快速排序算法,在面试的准备过程中,快排也一定是一个必须要牢牢掌握的算法。那么今天就来唠唠快速排序算法。

1012
来自专栏北京马哥教育

史上最简单!冒泡、选择排序的Python实现及算法优化详解

1、排序概念 内部排序和外部排序 根据排序过程中,待排序的数据是否全部被放在内存中,分为两大类: 内部排序:指的是待排序的数据存放在计算机内存中进行的排序过程;...

4994
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

2515
来自专栏fangyangcoder

算法导论中的四种基本排序

                                                        by方阳

1122
来自专栏Python小屋

Python模拟大整数乘法的小学竖式计算过程

让我们先看个图回顾一下小学学过的计算整数乘法的竖式计算过程 ? 然后再来看如何使用Python来模拟上面的过程,虽然在Python中计算任意大的数字乘法都没有问...

3275
来自专栏计算机视觉与深度学习基础

Leetcode 287. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 a...

3454
来自专栏HTML5学堂

原生JS | 当兔子遇到鸡

HTML5学堂-码匠:当兔子遇到鸡,会怎样呢?先别急,看个小视频~ 视频内容 当兔子遇到鸡 —— 不要害怕和别人不一样,在这个世界上,你就是独一无二的自己! 不...

44110
来自专栏Java帮帮-微信公众号-技术文章全总结

Java基础-06.总结二维数组,面向对象

1:二维数组(理解) (1)元素是一维数组的数组。 (2)格式: A:数据类型[][] 数组名 = new 数据类型[m][n]; B:数据类型[][]...

2664

扫码关注云+社区