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

查看所有标签

猜你喜欢:

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

Effective JavaScript

Effective JavaScript

David Herman / Addison-Wesley Professional / 2012-12-6 / USD 39.99

"It's uncommon to have a programming language wonk who can speak in such comfortable and friendly language as David does. His walk through the syntax and semantics of JavaScript is both charming and h......一起来看看 《Effective JavaScript》 这本书的介绍吧!

图片转BASE64编码
图片转BASE64编码

在线图片转Base64编码工具

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

RGB HSV 转换
RGB HSV 转换

RGB HSV 互转工具