【每日一题】LeetCode 189. 旋转数组

题目详情

题目描述

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1：

输入: [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]

示例 2：

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明

要求使用空间复杂度为O(1)的原地算法

题解

🙋‍♂️今日打卡～～

思路

拿到这道题，第一看过去，第一个想法是使用额外的空间，新申请一个一维数组用于保存当前需要移动的后半段元素，等待前半段元素在原始数组中移动到相应的位置之后，再把新数组的后半段元素移动到原数组的前半段。

题目下面的说明说是要求使用原地算法，就是不使用额外的空间。那就需要在原数组上下功夫，怎么才能让后半段元素变到前半段，前半段的元素变到后半段，确实需要想一想。想了一会，终于想通了，我们可以先把整个数组翻转，这样后半段元素已经变到前面了，只是后半段元素的位置是反的，还需要将翻转后的数组按照[0,k]和[k+1,n]翻转一次，这样就可以得到结果。

步骤

第一步，[0,n-1]数组长度整体翻转

第二步，[0,k-1]长度翻转

第三步，[k,n-1]长度翻转

注意

• K需要对数组长度进行取余，可以减少不必要的操作。

代码

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        k%=n;
        if(k==0){
            return;
        }
        reverse(nums,0,n-1);
        reverse(nums,0,k-1);
        reverse(nums,k,n-1);
    }
    private void reverse(int[] nums,int l,int r){
        while(l<r){
            int tmp = nums[l];
            nums[l] = nums[r];
            nums[r] = tmp;
            l++;
            r--;
        }
    }
}

总结

面对数组类型的题目，其实简单方法大部分人都可以想出来，只不过会有高时间复杂度，或者高空间复杂度，如果要优化，就需要认真思考。但是如果没有想出来最优解也不要太难受，因为有些东西是需要学习的，或者换句话说，需要看别人的题解，就好像是知识一样，没学过，不了解，很正常，我们只有见多了，看多了，把看过的吸收成自己的，这样才能提升自己。有做不错来的题，去把题解吃透吧。

写在后面

今天在疯狂循环播放《烟火里的尘埃》，不知道为什么我听这首歌的时候，并不会感觉到悲伤，而是感觉到一种气势磅礴，网抑云时间到了，“笑的开怀，哭的坦率，为何表情要让这世界安排”。还有就是最后那假音高音感觉确实像是腾空的烟火🎆，到最高点炸开。其实我之前是没有怎么听过他的歌的，只知道他是快乐男声出来的，纯路人，听完这首歌之后，感觉他还是很有能力的，小伙伴们可以去听听。

各位客官，走过路过，点个赞再走吧，感谢🙏
关注即可提高学习效率，关注不迷路