0189. 轮转数组

[utterances-bot]

0189. 轮转数组 | 算法通关手册

189. 轮转数组 # 标签：数组 难度：中等 题目大意 # 描述：给定一个数组 nums，再给定一个数字 k。
     要求：将数组中的元素向右移动 k 个位置。
     说明：
     $1 \le nums.length \le 10^5$。 $-2^{31} \le nums[i] \le 2^{31} - 1$。 $0 \le k \le 10^5$。 使用空间复杂度为 O(1) 的原地算法解决这个问题。 示例

https://algo.itcharge.cn/Solutions/0100-0199/rotate-array

[longlingking]

具体步骤3是否应该为[k,n-1]位置上的元素进行翻转

[itcharge]

具体步骤3是否应该为[k,n-1]位置上的元素进行翻转

嗯嗯。应该是 [k, n-1]。 感谢指正呀

[Ding12345678910]

写的很好，mark，按照这个顺序刷题了

[weibaozi]

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        start=0
        end=len(nums)-1
        length=end - start +1
        direction = 1  #0 for going left, 1 for going right
        k = k % length
        while(k != 0):
            # if k > length/2, rotate to opposite direction
            if 2* k > length:
                direction ^= 1
                k = length - k
            #swap k number between start and end
            for i in range(k):
                tmp=nums[start + i]
                nums[start + i] = nums[end - k + 1 + i]
                nums[end- k + 1 + i] = tmp
            start += k * direction
            end -= k * (direction^1)
            length= end - start + 1
            k = k % length

自己想了个办法,时间复杂度也是O(n)但是慢一点,感觉我这个cycle数会更小一点来着,平均1n个cycle.可以参考看看为什么嘛

[Lorenzy05]

我觉得这样的话 是很简便的

def Wheel_Array(array, k):
--for x in range(k):
----last = array[-1]
----array.insert(0, last)
----del array[-1]

--return array

[ginnylin516]

def rotate(nums, k):
L = [0 for i in range(len(nums))]
for i in range(len(nums)):

    q = i + k
    while q >= len(nums):
        q = i + k - len(nums)
    L[q] = nums[i]
    
return print（L）

我在pycharm上能实现 但在leetcode上报错 有人帮我看看吗！ 感谢

[itcharge]

start=0
        end=len(nums)-1
        length=end - start +1
        direction = 1  #0 for going left, 1 for going right
        k = k % length
        while(k != 0):
            # if k > length/2, rotate to opposite direction
            if 2* k > length:
                direction ^= 1
                k = length - k
            #swap k number between start and end
            for i in range(k):
                tmp=nums[start + i]
                nums[start + i] = nums[end - k + 1 + i]
                nums[end- k + 1 + i] = tmp
            start += k * direction
            end -= k * (direction^1)
            length= end - start + 1
            k = k % length

leetcode 上计算的是运行时间，只要复杂度一致，快一点慢一点不用太在意。

[itcharge]

def rotate(nums, k): L = [0 for i in range(len(nums))] for i in range(len(nums)):

    q = i + k
    while q >= len(nums):
        q = i + k - len(nums)
    L[q] = nums[i]
    
return print（L）

这道题并不需要返回数组，而是需要直接在原数组上进行修改。

[h-jm98]

可以用切片[::-1]代替翻转函数，会方便些

[Meng-37]

为什么这样会改变外部的nums，我用nums = nums[len(nums)-k:] + nums[:len(nums)-k]却改变不了？

[olong]

请问为何需要 k = k % n 这一步？

[Afeii1]

如果你要轮转的个数大于len(nums) 就会使得数组越界

[emptyttt]

for i in range(k):
nums.insert(0,nums[-1])
nums.pop(-1)

[eatingwanna]

class Solution(object):
def rotate(self, nums, k):
for i in range(0,k):
tmp=nums[len(nums)-1];
for j in range(len(nums)-1,0,-1):
nums[j]=nums[j-1];
nums[0]=tmp;
return nums;

[ZL-Asica]

直接把最后的k个元素slice一下放到最前面，然后删掉最后的k个元素，这样时间是O(k) [插入耗时]，空间是O(1)

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

[ZL-Asica]

包括这样也是一样的逻辑，原地直接换

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        k = k % n
        nums[:] = nums[-k:] + nums[:-k]