question:
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].
Hint:
Could you do it in-place with O(1) extra space?
link:https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/646/
解法1：
首先会想到的是新开一个数组,按照要求遍历数组nums,并且放到新的数组中去就可以了.
比如:[1,2,3,4,5,6] n=6 k=2 把数组分成两部分 [1,2,3,4,5,6] 分别放到新的数组中去就可以了
代码实现:
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]; } }
解法2：
这里有一个很巧妙的方法：
利用数组的length - k 把数组 分为两半；
reverse 左边和右边的数组；
reverse 总数组
举一个例子：
1 2 3 4 5 6 7 如果k = 3 的话， 会变成 5 6 7 1 2 3 4
1 2 3 4 5 6 7 middle = 7 - 3 = 4，分为左边 4个数字，右边 3个数字
4 3 2 1 7 6 5 分别把左右reverse 一下
5 6 7 1 2 3 4 把总数组reverse 一下就会得到答案
public class Solution { public void rotate(int[] nums, int k) { if(nums == null || nums.length == 0 || k % nums.length == 0) return; int turns = k % nums.length; int middle = nums.length - turns; reverse(nums, 0, middle-1); // reverse left part reverse(nums, middle, nums.length-1); // reverse right part reverse(nums, 0, nums.length-1); // reverse whole part } public void reverse(int[] arr, int s, int e) { while(s < e) { int temp = arr[s]; arr[s] = arr[e]; arr[e] = temp; s++; e--; } } }