题目

LeetCode 189 旋转数组

给定一个数组，将数组中的元素向右移动 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rotate-array

代码

方法一：暴力解法

  1. class Solution {
  2.     public void rotate(int[] nums, int k) {
  3.         int temp,previous;
  4.         for(int j=0;j<k;j++)
  5.         {
  6.             previous=nums[nums.length-1];
  7.             for(int i=0;i<nums.length;i++)
  8.             {
  9.                 temp=nums[i];
  10.                 nums[i]=previous;
  11.                 previous=temp;
  12.             }
  13.         }
  14.     }
  15. }

方法二：环形替换

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length; //一旦k超出数组长度，进行k次替换就相当于k%nums.length次
        int count = 0; //利用count统计替换元素的个数
        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;
                //替换完成后，被替换的元素存放在prev中，下一次将该元素向后替换
                count++;//替换一次累计统计
            } while (start != current);//当start==current时相当于本次替换完成（进入顺位第二的同学位置替换）
        }
    }
}

来自leetcode的一个评论解释该算法：

菜虚困：

把元素看做同学，把下标看做座位，大家换座位。第一个同学离开座位去第k+1个座位，第k+1个座位的同学被挤出去了，他就去坐他后k个座位，如此反复。但是会出现一种情况，就是其中一个同学被挤开之后，坐到了第一个同学的位置（空位置，没人被挤出来），但是此时还有人没有调换位置，这样就顺着让第二个同学换位置。 那么什么时候就可以保证每个同学都换完了呢？n个同学，换n次，所以用一个count来计数即可。