LeetCode100之轮转数组(189)--Java

1.问题描述

        给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

        示例1

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

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

        提示

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

        难度等级

                中等

        题目链接

                轮转数组

2.解题思路

        这道题轮转数组的题很有意思，它要将数组中的元素往右轮转k个位置(也就是将所有的元素往右移动k个单位，如果越界了，就补到数组前面)。相信大家看到这道题，肯定里面就想到用循环不断移就解决了，或者用队列存储前k个之后，再依次插入，都可以。这里我不过多介绍，我来介绍一种比较巧妙的方法，就是通过反转数组来解决这道题。

    //数组反转
    public void reverse(int[] nums,int start,int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }

        在介绍反转数组之前，我们要注意一点就是，k可以比数组的长度大，如果k刚好等于数组长度，轮转之后还是原数组，不信大家可以试试看，所以我们可以直接给k取模，得出实际需要轮转的次数。

        k = k % nums.length;

        不知道大家有没有发现，这里所谓的轮转数组，其实就是把数组后面的k个元素放到数组的前面来。也就是说我们可以根据k，将数组分为前面和后面两部分，把后面的部分放到前面的部分就可以了。所以我们可以直接将数组整个反转，这样原本前面的数就跑到后面了，后面的数就跑到前面了。但是反转之后，我们发现这两组内部的顺序因为我们反转了数组也跟着改变了，但没关系，我们就对这两组各自再进行一次反转，这么它们内部的顺序又变回来了，而我们也得到了我们要的答案。

        //将整个数组反转
        reverse(nums,0,nums.length-1);
        //反转前k个数
        reverse(nums,0,k-1);
        //反转剩余的数
        reverse(nums,k,nums.length-1);

3.代码展示

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;
        //将整个数组反转
        reverse(nums,0,nums.length-1);
        //反转前k个数
        reverse(nums,0,k-1);
        //反转剩余的数
        reverse(nums,k,nums.length-1);
    }
    //数组反转
    public void reverse(int[] nums,int start,int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

4.总结

        这道题的解法有很多，反转数组这种解法可以说是很巧妙了，大家可以尝试一下。如果实在不理解，把三次反转各自的结果写一遍，就明白了。好了，这道题就说到这了，咱们下一题再见~