本文共 2455 字，大约阅读时间需要 8 分钟。

题目

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3

Output: [5,6,7,1,2,3,4]

Explanation:

rotate 1 steps to the right: [7,1,2,3,4,5,6]

rotate 2 steps to the right: [6,7,1,2,3,4,5]

rotate 3 steps to the right: [5,6,7,1,2,3,4]

我的想法

先把数组尾部会被移到头部的元素取出，再按照步长移动数组内元素，最后将取出的元素补回头部

class Solution {
       public void rotate(int[] nums, int k) {
           if(nums.length == 1 || k == 0) return;        		k = k%nums.length; //去除周期        int[] buff = new int[k];        for(int i = 0; i < k; i++){
               int index = nums.length - k + i;            buff[i] = nums[index];        }        for(int i = nums.length - 1; i > k-1; i--){
               int index = i - k;            nums[i] = nums[index];        }        for(int i = 0; i < k; i++){
               nums[i] = buff[i];        }    }}

解答

leetcode solution 1：Using Extra Array

public class Solution {
       public void rotate(int[] nums, int k) {
           int[] a = new int[nums.length];        for (int i = 0; i < nums.length; i++) {
               a[(i + k) % nums.length] = nums[i];        }        for (int i = 0; i < nums.length; i++) {
               nums[i] = a[i];        }    }}

leetcode solution 2：Using Cyclic Replacements

public class Solution {
       public void rotate(int[] nums, int k) {
           k = k % nums.length;        int count = 0;        for (int start = 0; count < nums.length; start++) {
               int current = start;            int prev = nums[start];            do {
                   int next = (current + k) % nums.length;                int temp = nums[next];                nums[next] = prev;                prev = temp;                current = next;                count++;            } while (start != current);        }    }}

leetcode solution 3：Using Reverse

public class Solution {
       public void rotate(int[] nums, int k) {
           k %= nums.length;        reverse(nums, 0, nums.length - 1);        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--;        }    }}

转载地址：http://mfqvb.baihongyu.com/