数组旋转力扣#189

Question

Leetcode上的数组旋转题，为什么只用k %= len(nums)？

def rotate(nums, k):
    
    k %= len(nums)
    
    for i in range(k):
        previous = nums[-1]
        for j in range(len(nums)):
            nums[j], previous = previous, nums[j]
            
    return nums

Answer 1

如果将数组旋转 n，其中 n == len(array) 您实际上是在创建相同的数组，如下所示：

arr = [1,2,3]
k = 3
1. [3,1,2]
2. [2,3,1]
3. [1,2,3] # as you can see, this array is the same as the original

这意味着我们可以避免多余的旋转，只旋转 k % len(arr)。

示例：

arr = [1,2,3]
k = 5
1. [3,1,2]
2. [2,3,1]
3. [1,2,3] # this equals the original
4. [3,1,2] # this equals step 1
5. [2,3,1] # this equals step 2

# Since 5 % len(arr) = 5 % 3 = 2
# and since step 5 is the same as step 2
# we can avoid the redundant repetition
# and go for k % len(arr) = 2 from the start

数组旋转力扣#189

Array Rotation Leetcode#189

python

arrays

algorithm

data-structures