leetcode 189. 轮转数组

一、题目描述

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

二、示例

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

三、实现

方法1 暴力求解

数组每次右旋一个数，右旋k次

1.保存最后一个数
2.前面所有数字右移
3.将保存的最后一个数放到第一个位置

void rotate(int* nums, int numsSize, int k) {k %= numsSize;for (int i = 0; i < k; ++i) {// 1.保存最后一个数int temp = nums[numsSize - 1];// 2.前面所有数字右移for (int j = numsSize - 2; j >= 0; j--) {nums[j + 1] = nums[j];}// 3.将保存的最后一个数放到第一个位置nums[0] = temp;}
}

方法2 空间换时间

新申请一块空间，用于数据交换。

1.申请新空间
2.原数组前 size-k 个数移到新空间的后面
3.原数组最后 k 个数移到新空间的前面
4.新空间数据覆盖原数组

void rotate(int* nums, int numsSize, int k) {k %= numsSize;// 1.申请新空间int* tmp = (int*)malloc(numsSize * sizeof(int));// 2.原数组前 size-k 个数移到新空间的后面memcpy(tmp + k, nums, (numsSize - k) * sizeof(int));// 3.原数组最后 k 个数移到新空间的前面memcpy(tmp, nums + numsSize - k, k * sizeof(int));// 4.新空间数据覆盖原数组memcpy(nums, tmp, numsSize * sizeof(int));free(tmp);tmp = NULL;
}

方法3 三次逆置

原数组的下列三个区间数据逆置：
[0, size - k - 1]
[size - k, size - 1]
[0, size - 1]

// [begin, end]区间内数据逆置
void reverse(int* nums, int begin, int end) {while(begin < end) {int temp = nums[begin];nums[begin] = nums[end];nums[end] = temp;begin++;end--;}
}
void rotate(int* nums, int numsSize, int k){k %= numsSize;// 1.[0, size - k - 1]逆置reverse(nums, 0, numsSize-k-1);// 2.[size - k, size - 1]逆置reverse(nums, numsSize-k, numsSize-1);// 3.整体逆置reverse(nums,0, numsSize-1);
}