Rotate Array 旋转数组

题目本身容易理解，但要求 O(1)，并且想出3种方法。
方法一：数学规律
容易想到使用数学规律计算移动后的下标，但会有一个坑

  1. public void rotate(int[] nums, int k) {
  2.     int i = 1, j = 1, base = 0;
  3.     while (i <= nums.length) {
  4.         int to = k * j % nums.length + base;
  5.         if (to == base) {
  6.             base += 1;
  7.             j = 1;
  8.         } else {
  9.             int tmp = nums[base];
  10.             nums[base] = nums[to];
  11.             nums[to] = tmp;
  12.             j += 1;
  13.         }
  14.         i += 1;
  15.     }
  16. }

方法二：最大公约数
使用辗转相除法计算 gcd，减少移动的次数

  1. public void rotate(int[] nums, int k) {
  2.     k %= nums.length; // 处理 k > 数组长度的情况
  3.     int i = 0, gcd = gcd(k, nums.length);
  4.     while (i < gcd) {
  5.         int tmp = nums[i], j = i;
  6.         while (true) {
  7.             int s = j + k;
  8.             if (s >= nums.length) {
  9.                 s = s - nums.length;
  10.             }
  11.             if (s == i) {
  12.                 break;
  13.             }
  14.             nums[j] = nums[s];
  15.             j = s;
  16.         }
  17.         nums[j] = tmp;
  18.         i += 1;
  19.     }
  20. }
  22. public int gcd (int a, int b) {
  23.     return b == 0 ? a : gcd(b, a % b);
  24. }

方法三：多次反转
另辟蹊径的方法，感觉适合用在字符串上

  1. public void rotate(int[] nums, int k) {
  2.     int n = nums.length;
  3.     k %= length;
  4.     reverse(nums, 0, n - 1); //先反转全部的元素
  5.     reverse(nums, 0, k - 1); //在反转前k个元素
  6.     reverse(nums, k, n - 1); //接着反转剩余的
  7. }
  9. //把数组中从[start，end]之间的元素两两交换,也就是反转
  10. public void reverse(int[] nums, int start, int end) {
  11.     while (start < end) {
  12.         int tmp = nums[start];
  13.         nums[start] = nums[end];
  14.         nums[end] = tmp;
  15.         start += 1;
  16.         end -= 1;
  17.     }
  18. }