Rotate Array

描述

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

分析

最简单的方法，开一个k长的数组，先把右边k个元素存入这个临时数组，然后把数组中的前n-k右移k位，再把临时数组的k个元素存入到原始数组左边。时间复杂度O(n)，空间复杂度O(k)。

第二个简单的方法，先实现一个函数，把数组右移一位，调用这个函数k次即可。时间复杂度O(n*k)，空间复杂度O(1)。

第三个方法，先将数组分为两段，前n-k个为一段，后k个元素作为第二段，将第一段reverse, 第二段 reverse, 然后将整个数组reverse, 这样经过三轮reverse，就完成了循环右移。时间复杂度O(n)，空间复杂度O(1)。

解法1 三轮reverse

  1. // Rotate Array
  2. // Time Complexity: O(n), Space Complexity: O(1)
  3. public class Solution {
  4.     public void rotate(int[] nums, int k) {
  5.         k %= nums.length;
  6.         reverse(nums, 0, nums.length - k);
  7.         reverse(nums, nums.length - k, nums.length);
  8.         reverse(nums, 0, nums.length);
  9.     }
  10.     private static void reverse(int[] nums, int begin, int end) {
  11.         int left = begin;
  12.         int right = end - 1;
  13.         while (left < right) {
  14.             // swap
  15.             int tmp = nums[left];
  16.             nums[left] = nums[right];
  17.             nums[right] = tmp;
  18.             ++left;
  19.             --right;
  20.         }
  21.     }
  22. }

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/linear-list/array/rotate-array.html