给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。 复制代码
示例:
输入: [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] 输入: [-1,-100,3,99] 和 k = 2 输出: [3,99,-1,-100] 解释: 向右旋转 1 步: [99,-1,-100,3] 向右旋转 2 步: [3,99,-1,-100] 复制代码
思考:
这道题有一种巧妙地利用反转的做法。 首先将第0个到第k个元素反转,再将第k+1到末尾元素反转,最后再将全部元素反转即可。 例如:[1,2,3,4,5,6,7] k = 3 将0到3反转:[4,3,2,1,5,6,7] 将4到6反转:[4,3,2,1,7,6,5] 全部翻转:[5,6,7,1,2,3,4] 得到最后结果。 这里要注意下还有这样的情况:[1,2] k = 5 即k大于数组长度的情况。 这里可以发现数组旋转次数等于数组长度时,旋转后的数组与初始数组相同,转了一圈又回来了。 1次旋转:[2,1] 2次旋转: [1,2] 转回来了 3次旋转:[2,1] 4次旋转: [1,2] 转回来了 5次旋转:[2,1] 所以这里的有效k等于k对数组长度求余。 复制代码
实现:
class Solution { public void rotate(int[] nums, int k) { int length = nums.length; k %= length; reverse(nums, 0, length - 1); reverse(nums, 0, k - 1); reverse(nums, k, length - 1); } private void reverse(int[] nums, int start, int end) { while (start < end) { int temp = nums[start]; nums[start++] = nums[end]; nums[end--] = temp; } } }复制代码
以上所述就是小编给大家介绍的《LeetCode每日一题: 旋转数组(No.189)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- 菜鸡的算法修炼:数组(旋转数组的最小数字)
- leetcode - 189. 旋转数组
- C++ 和 Python 实现旋转数组的最小数字
- LeetCode - 189 - 旋转数组(rotate-array)
- C语言数组中字符串的旋转(左旋与右旋)
- 【Leetcode】61.旋转链表
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
Algorithms and Data Structures
Kurt Mehlhorn、Peter Sanders / Springer / 2008-08-06 / USD 49.95
Algorithms are at the heart of every nontrivial computer application, and algorithmics is a modern and active area of computer science. Every computer scientist and every professional programmer shoul......一起来看看 《Algorithms and Data Structures》 这本书的介绍吧!
CSS 压缩/解压工具
在线压缩/解压 CSS 代码
html转js在线工具
html转js在线工具