leetcode 热题 100_轮转数组

题解一：

        新数组存储：另外用一个数组存储移动后的结果，再复制回原数组。

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

题解二：

        原数组移动：在原数组上直接将nums[i]移动到nums[i+k]，需要临时存储被覆盖的值nums[i+k]，被覆盖的值则继续向后移动覆盖nums[i+2k]，循环直到回到第一个开始移动的值。，这个过程可能有若干元素没有被移动，因此需要从nums[i+1]开始重复这个过程。如何判断所有的值都被移动过一次呢，另外用一个count计数，每次移动都+1，直到等于数组长度。这个解法效率较低并且较难理解，不推荐。

class Solution {public void rotate(int[] nums, int k) {int n = nums.length;k = k % n;int count = 0;for (int i = 0; count < n; i++) {for (int pre = nums[i], next, index = i; ; ) {next = (i + k) % n;int temp = nums[next];nums[next] = pre;pre = temp;count++;i = (i + k) % n;if (i == index) break;}}}}

题解三：

        数组翻转：将整个数组进行反转，再以下标[0,k-1]，[k,nums.length-1]左右两段分别进行翻转就得到最终结果，很巧妙的解法。

class Solution {public void reserve(int[] a, int begin, int end) {for (; begin < end; begin++, end--) {int temp = a[begin];a[begin] = a[end];a[end] = temp;}}public void rotate(int[] nums, int k) {k = k % nums.length;reserve(nums, 0, nums.length-1);reserve(nums, 0, k - 1);reserve(nums, k, nums.length-1);}
}