数组的翻转与轮转

Question

当前存在一个数组nums，编写算法将数组中的 个元素向右轮转 个位置（ 为非负数）。

为了避免直接轮转导致的数组元素覆盖，可以创建新的数组从而将中的元素存储至正确的位置，尔后再将其赋值至原数组中。在轮转过程中，当数组元素向右移动 个位置后，数组末端的 个元素将移动至数组首端，而剩余元素则向后移动 个位置。因此，可以通过翻转的方式将数组末端的元素移动至数组首端，而同时数组首端的元素将被翻转至数组末端。以数组[1, 2, 3, 4, 5, 6, 7]为例，其轮转过程为

• 将所有数组元素翻转

• 翻转区间内的元素

• 翻转区间内的元素

翻转操作本质上为互换操作。因此，需要定义一个临时变量temp用于替换操作。互换函数为

void swap(int* a, int* b){
  int temp = *a;
  *a = *b, *b = t;
}

持有互换函数后，需在翻转函数中确定互换的元素对象。翻转函数为

void reverse(int* nums, int low, int high){
  while(low < high){
    swap(&nums[low], &nums[high]);
    low++;
    high--;
  }
}

因此，根据分析结果，轮转函数为

void rotate(int* nums, int numsSize, int k){
  k %= numsSize;  //避免k值大于数组长度
  reverse(nums, 0, numsSize - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, numsSize - 1);
}

完整代码为

void swap(int* a, int* b){
  int temp = *a;
  *a = *b, *b = t;
}

void reverse(int* nums, int low, int high){
  while(low < high){
    swap(&nums[low], &nums[high]);
    low++;
    high--;
  }
}

void rotate(int* nums, int numsSize, int k){
  k %= numsSize;
  reverse(nums, 0, numsSize - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, numsSize - 1);
}

Python下该算法代码为

class Solution(object):
  def rotate(self, nums, k):
    n = len(nums)
    k %= n
    nums[:] = nums[::-1]
    nums[:k] = nums[:k][::-1]
    nums[k:] = nums[k:][::-1]

更好的方法为通过slice操作拼接数组

class Solution(object):
  def rotate(self, nums, k):
    n = len(nums)
    k %= n
    nums[:] = nums[-k:] + nums[:-k]