旋转数组（数组整体右移k位）

本文主要是介绍旋转数组（数组整体右移k位），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
进阶：
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？
作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

一开始想到了构建一个新数组作为结果，然后每个元素直接按（当前位置 + k）% length 得到右移之后的新位置放到新数组内作为结果返回。
不过这个方法显然不能原地工作Orz。
于是又想到可以只用一个临时变量存储队尾元素，然后每个元素右移一位，最后临时变量放置到对头，这样进行k轮。结果这种方法还超时了。。。

/**
     * 向右移动元素，每次移动一位，移动k次
     * 从后向前开始移动，所以暂存队尾元素，一轮移动完毕后，暂存元素放至队首
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k){
        int len = nums.length;
        if(len <= 1){
            return;
        }
        while(k > 0){
            int temp = nums[len - 1];//暂存最后一位元素
            for(int i = len - 2; i >= 0; i--){ //从倒数第二位元素开始，依次右移
                nums[i + 1] = nums[i];
            }
            nums[0] = temp;
            k--;
        }
    }

然后看一下题解，竟然翻转三次数组就可以办到！

/**
     * 反转三次
     * 1.整体反转1次
     * 2.前k个元素反转依次
     * 3.其余元素反转一次
     * 上述步骤相当于所有元素右移k位
     * @param nums
     * @param k
     */
    public static void rotate(int[] nums, int k){
        int len = nums.length;
        if(len <= 1){
            return;
        }
        k %= len;
        reverse(nums,0, nums.length - 1);
        reverse(nums, 0, k - 1); //前k个元素对应的下标 个数转下标要-1
        reverse(nums, k, nums.length - 1);
    }

    /**
     * 反转数组[begin, end]范围内的元素
     * @param array
     * @param begin
     * @param end
     */
    public static void reverse(int[] array, int begin, int end){
        while(begin < end){
            int temp = array[end];
            array[end--] = array[begin];
            array[begin++] = temp;
        }
    }

这个方法真的太妙了，那若是数组左移k位怎么办呢？只需要旋转后k个元素和其余元素就可以，代码如下

/**
     * 1.数组整体反转一遍
     * 2.第二次反转后k个元素
     * 3.第三次反转剩余元素
     * @param nums
     * @param k
     */
    public static void rotate2(int[] nums, int k){
        int len = nums.length;
        if(len <= 1){
            return;
        }
        k %= len;
        int d = len - k; //此时d之后有k个元素，故d为分界线
        reverse(nums,0, len - 1);
        reverse(nums, 0, d - 1); //前k个元素对应的下标 个数转下标要-1
        reverse(nums, d, len - 1);
    }

这篇关于旋转数组（数组整体右移k位）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！