189. Rotate Array

题目描述和难度

  • 题目描述：

给定一个数组，将数组中的元素向右移动 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) 的原地算法。

思路分析

求解关键：

$3$ 次逆转即可，别忘了极端条件判断。

参考解答

参考解答1

Java 写法：

import java.util.Arrays;

public class Solution {

    // 向右旋转
    // 输入: [1,2,3,4,5,6,7] 和 k = 3

    // 结果：[5,6,7,1,2,3,4]

    // 中间过程：
    // 7 6 5 4 3 2 1
    // 5 6 7 1 2 3 4

    public void rotate(int[] nums, int k) {
        // 先写出极端条件
        int len = nums.length;
        if (len == 0 || k <= 0) {
            return;
        }

        k %= len;

        reverse(nums, 0, len - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, len - 1);
    }

    private void reverse(int[] nums, int index1, int index2) {
        if (index1 >= index2) {
            return;
        }
        while (index1 < index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
            index1++;
            index2--;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 2, 3, 4, 5, 6, 7};
        int k = 3;
        Solution solution = new Solution();
        solution.rotate(nums, k);
        System.out.println(Arrays.toString(nums));
    }
}

Python 写法：

class Solution:
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: void Do not return anything, modify nums in-place instead.
        """

        # 先处理极端情况

        if len(nums) == 0 or k <= 0:
            return

        k = k % len(nums)

        # 做下面 3 个逆转动作的时候，注意边界条件
        # 技巧就是举具体的例子
        self.__reverse(nums, 0, len(nums) - 1)
        self.__reverse(nums, 0, k - 1)
        self.__reverse(nums, k, len(nums) - 1)

    def __reverse(self, nums, index1, index2):
        """
        将数组 [index1,index2] 区间内的元素进行逆转
        :param nums:
        :param index1:
        :param index2:
        :return:
        """

        while index1 < index2:
            nums[index1], nums[index2] = nums[index2], nums[index1]
            index1 += 1
            index2 -= 1


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5, 6, 7]
    k = 3

    s = Solution()
    s.rotate(nums, k)
    print(nums)

本篇文章的地址为 https://liweiwei1419.github.io/leetcode-solution/leetcode-0189-rotate-array ，如果我的题解有错误，或者您有更好的解法，欢迎您告诉我 liweiwei1419@gmail.com 。