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

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

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

查看所有标签

猜你喜欢:

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

C语言进阶

C语言进阶

牟海军 / 机械工业出版社 / 2012-7 / 59.00元

C语言是编程语言中的一朵奇葩,虽已垂垂老矣,但却屹立不倒,诞生了数十年,仍然是最流行的编程语言之一。C语言看似简单,却不易吃透,想要运用好,更是需要积淀。本书是一本修炼C程序设计能力的进阶之作,它没有系统地去讲解C语言的语法和编程方法,而是只对C语言中不容易被初学者理解的重点、难点和疑点进行了细致而深入的解读,揭露了C语言中那些鲜为普通开发者所知的秘密,旨在让读者真正掌握C语言,从而编写出更高质量......一起来看看 《C语言进阶》 这本书的介绍吧!

RGB转16进制工具
RGB转16进制工具

RGB HEX 互转工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换