1 //给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
2 //
3 // 示例 1:
4 //
5 // 输入: [1,2,3,4,5,6,7] 和 k = 3
6 //输出: [5,6,7,1,2,3,4]
7 //解释:
8 //向右旋转 1 步: [7,1,2,3,4,5,6]
9 //向右旋转 2 步: [6,7,1,2,3,4,5]
10 //向右旋转 3 步: [5,6,7,1,2,3,4]
11 //
12 //
13 // 示例 2:
14 //
15 // 输入: [-1,-100,3,99] 和 k = 2
16 //输出: [3,99,-1,-100]
17 //解释:
18 //向右旋转 1 步: [99,-1,-100,3]
19 //向右旋转 2 步: [3,99,-1,-100]
20 //
21 // 说明:
22 //
23 //
24 // 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
25 // 要求使用空间复杂度为 O(1) 的 原地 算法。
26 //
27 // Related Topics 数组
28 // ?? 692 ?? 0
29
30
31 //leetcode submit region begin(Prohibit modification and deletion)
32 class Solution {
33 public void rotate(int[] nums, int k) {
34 int len = nums.length;
35 k %= len;
36 int count = 0;
37 for(int start = 0; count < len; start++){
38 int next = (start + k) % len;//将要被替换的位置
39 int pre = nums[start];
40 do{
41 int temp = nums[next];//将将要被替换的元素记录下来
42 nums[next] = pre;//进行替换
43 pre = temp;//被替换出来的元素在下一轮要成为替换别人的元素
44 next = (next + k) % len;//计算出下一个要被替换的元素
45 count++;
46 }while (next != start);
47 nums[next] = pre;//处理边界
48 count++;//每进行一次替换count就要+1
49 }
50 }
51 }
52 //leetcode submit region end(Prohibit modification and deletion)
53 //info
54 // 解答成功:
55 // 执行耗时:0 ms,击败了100.00% 的Java用户
56 // 内存消耗:39.4 MB,击败了48.25% 的Java用户