【LeetCode每日一题】—

【LeetCode每日一题】——189.轮转数组

文章目录

一【题目类别】
二【题目难度】
三【题目编号】
四【题目描述】
五【题目示例】
六【题目提示】
七【题目进阶】
八【解题思路】
九【时空频度】
十【代码实现】
十一【提交结果】

一【题目类别】

数组

二【题目难度】

中等

三【题目编号】

189.轮转数组

四【题目描述】

给定一个整数数组 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 <= 10^5$
$2^{31} <= nums[i] <= 2^{31} - 1$
$0 <= k <= 10^5$

七【题目进阶】

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

八【解题思路】

假设需要轮转k个位置，那么我们需要进行三次翻转：
- 第一次翻转：翻转整个数组，此时需要移动的元素已经到了数组的开始，其余元素在数组的后面
- 第二次翻转：将第一次翻转到数组开始的k个元素翻转，这样就变成了正常的顺序
- 第三次翻转，将第一次翻转到数组后面的剩余元素翻转，这样也变成了正常的顺序
当然，我们还要合理的处理k以避免溢出
该题不需要返回结果
具体细节可以参考下面的代码

九【时空频度】

时间复杂度： $O (n)$ ， $n$ 为传入的数组的长度
空间复杂度： $O (1)$

十【代码实现】

Java语言版

class Solution {public void rotate(int[] nums, int k) {// 防止溢出int n = nums.length;k %= n;// 第一次翻转：翻转整个数组，此时需要移动的元素已经到了数组的开始，其余元素在数组的后面reverse(nums, 0, n - 1);// 第二次翻转：将第一次翻转到数组开始的k个元素翻转，这样就变成了正常的顺序reverse(nums, 0, k - 1);// 第三次翻转，将第一次翻转到数组后面的剩余元素翻转，这样也变成了正常的顺序reverse(nums, k, n - 1);}// 翻转数组private void reverse(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}}

Python语言版

class Solution:def rotate(self, nums: List[int], k: int) -> None:# 防止溢出k %= len(nums)# 第一次翻转：翻转整个数组，此时需要移动的元素已经到了数组的开始，其余元素在数组的后面self.reverse(nums, 0, len(nums) - 1)# 第二次翻转：将第一次翻转到数组开始的k个元素翻转，这样就变成了正常的顺序self.reverse(nums, 0, k - 1)# 第三次翻转，将第一次翻转到数组后面的剩余元素翻转，这样也变成了正常的顺序self.reverse(nums, k, len(nums) - 1)# 翻转数组def reverse(self, nums, start, end):while start < end:temp = nums[end]nums[end] = nums[start]nums[start] = tempstart += 1end -= 1

C语言版

// 翻转数组
void reverse(int* nums, int start, int end)
{while (start < end){int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}
}void rotate(int* nums, int numsSize, int k)
{// 防止溢出k %= numsSize;// 第一次翻转：翻转整个数组，此时需要移动的元素已经到了数组的开始，其余元素在数组的后面reverse(nums, 0, numsSize - 1);// 第二次翻转：将第一次翻转到数组开始的k个元素翻转，这样就变成了正常的顺序reverse(nums, 0, k - 1);// 第三次翻转，将第一次翻转到数组后面的剩余元素翻转，这样也变成了正常的顺序reverse(nums, k, numsSize - 1);
}