文章目录

• • 🐨1. 题目
  • 🌻2. 解法1-开辟新数组
  • • 🌼2.1 思路
    • 🌼2.2 代码实现
  • 🌴3.解法2-翻转法
  • • 🌱3.1 思路
    • 🌱3.2 代码实现

🐨1. 题目

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

示例1：

输入: 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]

示例2：

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

🌻2. 解法1-开辟新数组

🌼2.1 思路

创建一个新的数组，先将需逆置的数逐个放入，再将剩下的数依次放入，最后将新数组的内容拷贝到原数组。

开辟了n个空间，空间复杂度为O(n)
放入n次，时间复杂度为O(n)

🌼2.2 代码实现

void rotate(int* nums, int numsSize, int k) {assert(nums);//减少无意义的轮转，同时防止边界异常k = k % numsSize;int* newNum = (int*)malloc(sizeof(int) * numsSize);int cur = 0;for (int i = numsSize - k; i < numsSize; i++){newNum[cur++] = nums[i];}memcpy(newNum + cur, nums, sizeof(int) * (numsSize - k));memcpy(nums, newNum, sizeof(int) * numsSize);
}

🌴3.解法2-翻转法

🌱3.1 思路

这里我们发现，先将前n-k个逆置，再将后k个逆置，最后再整体逆置，即得到了我们想要的结果。此时，没有开辟额外的空间。

空间复杂度:O(1)
时间复杂度：O(n)

🌱3.2 代码实现

void reverse(int* nums, int left, int right)
{while (left < right){int tmp = nums[left];nums[left] = nums[right];nums[right] = tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {assert(nums);k = k % numsSize;//逆置前n-k个reverse(nums, 0, numsSize - k - 1);//逆置后k个reverse(nums, numsSize - k, numsSize - 1);//整体逆置reverse(nums, 0, numsSize - 1);
}