文档章节

旋转数组 Rotate Array

叶枫啦啦
 叶枫啦啦
发布于 2017/06/06 16:15
字数 533
阅读 3
收藏 0

问题:

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.

Hint:

Could you do it in-place with O(1) extra space?

Related problem: Reverse Words in a String II

 

【解析】将数组元素向前移动K步得到的新的数组。

解决:

①首先,数组移动K个位置后下标值为(i + k) % n,新建一个数组,将数值依次移动到对应的位置,这种方法的空间复杂度为O(n).耗时1ms。

public class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] arr = new int[n];
        for (int i = 0;i < n ;i ++ ) {
            arr[(i + k) % n] = nums[i];
        }
        for (int i = 0;i < n ;i ++ ) {
            nums[i] = arr[i];
        }
    }
}

②类似于冒泡排序,将数组依次向后移动k次即可。时间复杂度为O(n*k)。超时

public class Solution {  
    public static void rotate(int[] nums, int k) {
        for (int i = 0;i < k; i ++) {
            int tmp = nums[nums.length - 1];
            for (int i = nums.length - 1;i > 0 ;i -- ) {
                nums[i] = nums[i - 1];
            }
            nums[0] = tmp;
        }
    }
}  
③可以通过三次反转数组实现。第一次反转整个数组,第二次反转前K个数组,第三次反转剩余的数组。这种方法不需要额外的空间,空间复杂度为O(1)。耗时2ms。

例如:

一维数组[1,2,3,4,5,6,7],k=3

第一次反转:7,6,5,4,3,2,1

第二次反转:5,6,7,4,3,2,1

第三次反转:5,6,7,1,2,3,4 ----- 最终结果

public class Solution {  
    public void rotate(int[] nums, int k) {  
        k %= nums.length;//k值超过数组长度时  
        reverse(nums,  0, nums.length-1);//翻转整个数组  
        reverse(nums, 0, k-1);//翻转前k个数  
        reverse(nums, k, nums.length-1);//翻转剩下的数  
    }  
    public void reverse(int[] nums, int start, int end) {  
        while (start < end) {  
            int temp = nums[start];  
            nums[start] = nums[end];  
            nums[end] = temp;  
            start++;  
            end--;  
        }  
    }  
}  
④同理,进行三次翻转。

以n - k为界,分别对数组的左右两边执行一次逆置;然后对整个数组执行逆置。

reverse(nums, 0, n - k - 1)
reverse(nums, n - k, n - 1)
reverse(nums, 0, n - 1)

 

© 著作权归作者所有

叶枫啦啦
粉丝 14
博文 583
码字总数 400448
作品 0
海淀
私信 提问
【Leetcode】【简单】【189. 旋转数组】【JavaScript】

题目描述 189. 旋转数组 给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: [1,2,3,4,5,6,7] 和 k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右旋转 1 步: [7,1,2,...

孙达
09/04
0
0
Codility每周一课:L2 Arrays(P2.2)

P2.2 CyclicRotation Rotate an array to the right by a given number of steps. P2.2 旋转 数组旋转给定次数 由N个整数组成的数组A。数组的一次旋转就是每个元素均向右移动一个位置,数组的...

AiFan
01/17
0
0
【LeetCode】396. Rotate Function(java实现)

原题链接 https://leetcode.com/problems/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......

BookShu
2016/11/16
65
0
php+jquery实现转盘抽奖 概率可任意调

php+jquery实现转盘抽奖 概率可任意调 php+jquery实现转盘抽奖 概率可任意调 Posted by: xiaomiao 2014/05/13in Code, PHP 3 Comments php+jquery实现转盘抽奖 查看DEMO演示 转盘抽奖,炫丽的...

蜗牛奔跑
2015/07/22
3.7K
0
Leetcode In Golang

LeetCode Problems' Solutions LeetCode Problems 1. Two Sum 题意:给出一个数组(数字不重复)和目标值,输出数组元素和为目标值的两个元素的下标,当且仅当只有一个解。 思路: 1.暴力算法 ...

SpiffyEight77
2018/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

ERC-777以太坊新代币标准解读

ERC777是一个新的高级代币标准,可以视为ERC20的升级版本,因此它解决了ERC20以及ERC223存在的一些问题,开发者可以根据自己的具体需求进行选型。 1、使用ERC820进行合约注册 有别于ERC20的自...

汇智网教程
今天
6
0
代理模式之JDK动态代理 — “JDK Dynamic Proxy“

动态代理的原理是什么? 所谓的动态代理,他是一个代理机制,代理机制可以看作是对调用目标的一个包装,这样我们对目标代码的调用不是直接发生的,而是通过代理完成,通过代理可以有效的让调...

code-ortaerc
今天
5
0
学习记录(day05-标签操作、属性绑定、语句控制、数据绑定、事件绑定、案例用户登录)

[TOC] 1.1.1标签操作v-text&v-html v-text:会把data中绑定的数据值原样输出。 v-html:会把data中值输出,且会自动解析html代码 <!--可以将指定的内容显示到标签体中--><标签 v-text=""></......

庭前云落
今天
8
0
VMware vSphere的两种RDM磁盘

在VMware vSphere vCenter中创建虚拟机时,可以添加一种叫RDM的磁盘。 RDM - Raw Device Mapping,原始设备映射,那么,RDM磁盘是不是就可以称作为“原始设备映射磁盘”呢?这也是一种可以热...

大别阿郎
今天
14
0
【AngularJS学习笔记】02 小杂烩及学习总结

本文转载于:专业的前端网站☞【AngularJS学习笔记】02 小杂烩及学习总结 表格示例 <div ng-app="myApp" ng-controller="customersCtrl"> <table> <tr ng-repeat="x in names | orderBy ......

前端老手
昨天
16
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部