動機
題目很賤,但賤的心服口服
reverse原來這麼泛用嗎?!
Problem
Given an array, rotate the array to the right by k
steps, where k
is non-negative.
Example 1:
Input: nums = [1,2,3,4,5,6,7], k = 3Output: [5,6,7,1,2,3,4]Explanation:rotate 1 steps to the right: [7,1,2,3,4,5,6]rotate 2 steps to the right: [6,7,1,2,3,4,5]rotate 3 steps to the right: [5,6,7,1,2,3,4]
Example 2:
Input: nums = [-1,-100,3,99], k = 2Output: [3,99,-1,-100]Explanation: rotate 1 steps to the right: [99,-1,-100,3]rotate 2 steps to the right: [3,99,-1,-100]
Constraints:
1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105
Follow up:
- Try to come up with as many solutions as you can. There are at least three different ways to solve this problem.
- Could you do it in-place with
O(1)
extra space?
Sol
如果老實的一個一個rotate,就會TLE
一個是Cyclic replace,就一直往前跳,直到再次回到起點
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
changed,i = 0,0
while changed < len(nums):
start,source = i, nums[i]
while True:
nextI = (start+k) % len(nums)
nums[nextI], source = source, nums[nextI]
start, changed = nextI, changed+1
if start == i:
break
i += 1
還有另一個是reverse
先整個reverse,再reverse要rotate的個數
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
def rev(ns,i,j):
while i < j:
ns[i], ns[j-1] = ns[j-1], ns[i]
i,j = i+1, j-1
rev(nums,0,len(nums))
rev(nums,0,k)
rev(nums,k,len(nums))