[Leetcode] Rotate Array 旋转数组

alighters 发布于2019-08-14 12:26 / 1131人阅读

摘要：反转法复杂度时间空间思路通过三次反转，我们可以很巧妙的实现旋转数组。首先我们将整个数组反转，然后将前个数字反转，然后再将后面剩下的数字反转，就得到目标数组了。而左旋时，我们是将其后个多带带反转，然后前面的多带带反转。

Rotate Array

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].

双数组 复杂度

时间 O(N) 空间 O(N)

思路

建立一个新数组，将位移过的数字放在新的数组中。

反转法 复杂度

时间 O(N) 空间 O(1)

思路

通过三次反转，我们可以很巧妙的实现旋转数组。首先我们将整个数组反转，然后将前k个数字反转，然后再将后面剩下的数字反转，就得到目标数组了。

注意

反转数组最简单的方法是交换元素，而交换元素有至少三种方法（临时变量，相加相减，异或）

k可能大于数组长度，旋转不止一次，所以我们要先对k取余

代码

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k-1);
        reverse(nums, k, nums.length-1);
    }
    
    private void reverse(int[] nums, int i, int j){
        while(i
后续 Follow Up
Q：如果是向左旋转k位而不是向右呢？
A：还是同样的方法，只是之前在反转完整个数组后，将其前k个多带带反转，后面的多带带反转。而左旋时，我们是将其后k个多带带反转，然后前面的多带带反转。

GPU云服务器云服务器旋转-rotate 数组array 数组Array类型旋转数组

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64479.html

LeetCode 189：旋转数组 Rotate Array

摘要：公众号爱写给定一个数组，将数组中的元素向右移动个位置，其中是非负数。只要截取输入的后位的数组与输入的剩余长度的数组，即为所求但是题目要求使用空间复杂度为的原地算法。利用切片切片组成新数组公众号：爱写bug（ID：icodebugs）给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 Given an array, rotate the array to the ...

cnsworder 2019-08-16 18:31 评论0 收藏0
LeetCode 189：旋转数组 Rotate Array

摘要：公众号爱写给定一个数组，将数组中的元素向右移动个位置，其中是非负数。只要截取输入的后位的数组与输入的剩余长度的数组，即为所求但是题目要求使用空间复杂度为的原地算法。利用切片切片组成新数组公众号：爱写bug（ID：icodebugs）给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。 Given an array, rotate the array to the ...

zhangrxiang 2019-07-31 11:26 评论0 收藏0
leetcode396. Rotate Function

摘要：题目要求代表对数组在位置上进行顺时针的旋转后生成的数组。暴力循环按照题目的要求，执行两次循环即可以获得的所有值，只需要从中比较最大值即可。题目要求 Given an array of integers A and let n to be its length. Assume Bk to be an array obtained by rotating the array A k p...

yintaolaowanzi 2019-08-16 13:50 评论0 收藏0
leetcode48 Rotate Image 90度旋转数组

摘要：每一次的旋转，其实都是正方形上的四个元素之间的相互替换。所以本质上我们只需遍历每种长度正方形上的一条边，就可以完成这个正方形的旋转。最后实现整个数组矩阵的旋转代表正方形的起始位置，即，，即，代表当前正方形上的一条边上的一个点。题目要求 You are given an n x n 2D matrix representing an image. Rotate the image b...

melody_lql 2019-08-16 10:34 评论0 收藏0
LeetCode 61：旋转链表 Rotate List

摘要：给定一个链表，旋转链表，将链表每个节点向右移动个位置，其中是非负数。按上述思路解，与旋转数组那道题大同小异，来介绍另一种很简单高效的方法。只需在第个节点之后切断，首尾连接即可。另外可能大于链表长度，应当做求余运算。给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 Given a linked list, rotate the list to the ...

Hwg 2019-07-31 11:30 评论0 收藏0