LeetCode每日一题: 旋转数组(No.189)

栏目: 编程工具 · 发布时间: 5年前

给定一个数组,将数组中的元素向右移动 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)》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Algorithms and Data Structures

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 压缩/解压工具

在线压缩/解压 CSS 代码

html转js在线工具
html转js在线工具

html转js在线工具