【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] = temp
            start += 1
            end -= 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);
}