“This is the 16th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

describe

Given an array, rotate the array to the right by k steps, where k is non-negative. 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?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] rotate 1 steps to the right: 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] rotate 3 steps to the right: [5,6,7,1,2,3,4]Copy the code

Example 2:

Input: nums = [-1,-100,3,99], k = 2 Output: [3,99,-1,-100] Explanation: rotate 1 steps to the right: Rotate 2 steps to the right: [99,-1,-100] rotate 2 steps to the right: [3,99,-1,-100]Copy the code

Note:

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5
Copy the code

parsing

Given an array, rotate the array k steps to the right, where k is non-negative. The question asks for more:

  • Try to come up with as many solutions as possible. There are at least three different ways to solve this problem
  • Do it in place with O(1) extra space

To use the extra space of O(1) means that changes can only be made in NUMS itself, and the first thought that came to mind was a very simple one. According to the description of the title, nums is regarded as a circle, and the result formed by k elements is rotated to the right.

  • I’m going to go through k times
  • Each traversal moves all elements of NUMS one bit to the right
  • The numS obtained after performing the above operations is the result.

The time complexity is O(k*N) and the space complexity is O(1).

answer

class Solution(object): def rotate(self, nums, k): """ :type nums: List[int] :type k: int :rtype: None Do not return anything, modify nums in-place instead. """ N = len(nums) k = k % N if k == 0 : Return nums for _ in range(k): t = nums[-1] for I in range(n-1,0,-1): nums[I] = nums[i-1] NUMs [0] = tCopy the code

The results

Time Limit Exceeded
Copy the code

parsing

In fact, reverse the following K elements to get T, and then assign nums[: n-k] to NUMs [k:], and then assign T to NUMs [:k] is also an operation in line with the topic. The spatial complexity of this solution is O(1), and the time complexity is O(N).

answer

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        N = len(nums)
        k = k % N
        if k == 0 : return nums
        t = nums[-k:]
        nums[k:] = nums[:N-k]
        nums[:k] = t
            
        
        
Copy the code

The results

The node is linked to the node in the linked list. Memory Usage: Submissions in the Python online list for Rotate Array.Copy the code

parsing

In fact, this problem can also be solved using a reversal of the law, as follows:

  • The initial array nums is represented as follows: 1, 2, 3, 4, 5, 6, 7
  • Start by reversing all the elements: 7, 6, 5, 4, 3, 2, 1
  • Invert the first K elements: 5, 6, 7, 4, 3, 2, 1
  • Invert the following n-k elements: 5, 6, 7, 1, 2, 3, 4

Therefore, we define a reverse function to perform the above three processes. It should be noted that k is modulo the length of nums, because if K is too large, we only need to know what k%len(nums) is, and many times of integer group movement has no effect on the result. Not only does it increase the computation, but it also makes the function not run correctly.

The time complexity is O(N), and the space complexity is O(1).

answer

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k %= len(nums)
        self.reverse(nums, 0, len(nums)-1)
        self.reverse(nums, 0, k-1)
        self.reverse(nums, k, len(nums)-1)
    
    def reverse(self, nums, start, end):
        while start<end:
            tmp = nums[start]
            nums[start] = nums[end]
            nums[end] = tmp
            start += 1
            end -= 1
Copy the code

The results

Given in the linked list. Memory Usage: Submissions in Python online submissions for Rotate Array.Copy the code

The original link

Leetcode.com/problems/ro…

Your support is my biggest motivation