时间戳

首页 > 解决方案 > 如何改进我的“旋转（滚动/循环排列）阵列”解决方案？

algorithm - 如何改进我的“旋转（滚动/循环排列）阵列”解决方案？

问题描述

我在 leetcode 上做了一些事情并提出了解决方案，它工作正常，但在某些情况下。这是问题本身：

在此处输入图像描述

但在这种情况下，它不会：

在此处输入图像描述

如果 k 大于数组的长度，如何旋转元素是没有意义的。如果您知道如何改进此解决方案，我将不胜感激

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        if len(nums) > k:
            self.swap(nums, 0, len(nums)-1)
            self.swap(nums, 0,k-1)
            self.swap(nums, k, len(nums)-1)


    def swap(self, nums, start, end):

        while start < end:
            nums[start], nums[end] = nums[end], nums[start]
            start+=1
            end-=1

标签： algorithmcircular-permutations

解决方案

k为了理解为什么这在大于数组长度的情况下不起作用，让我尝试解释旋转这些值背后的一些逻辑k。

模运算符%将很有用。例如，如果一个数组有 5 长，并且您想旋转 5，那么您最终会得到相同的数组。所以从技术上讲，您最好旋转 0。这就是%操作员发挥作用的地方。5 % 5 = 0. 如果我们想将一个长度为 5 的数组旋转 7 个点，我们最终会得到与将数组旋转 2 相同的结果，结果是7 % 5 = 2. 你知道我要去哪里吗？

k如果 的值小于数组的长度，这也成立。假设我们想将一个长度为 5 的数组旋转 3，我们会这样做3 % 5 = 3。

所以对于数量k和数组长度的任意旋转L，优化旋转量n等价于n = k % L。

您应该在旋转方法的开头修改代码以调整旋转量：

k = k % L

并使用此值旋转正确的数量。

推荐阅读