Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

The title

Given an array, move the elements of the array k positions to the right, where k is non-negative.

Advanced:

Come up with as many solutions as you can. There are at least three different ways to solve the problem.

Can you solve this problem with a spatial complexity O(1) in place algorithm?

The sample

Input: nums =,2,3,4,5,6,7 [1], k = 3 output:,6,7,1,2,3,4 [5] : spin to the right step 1:,1,2,3,4,5,6 [7] spin to the right step 2:,7,1,2,3,4,5 [6] to the right rotation step 3: ,6,7,1,2,3,4 [5] input: nums = [- 1-100,3,99], k = 2 output: [3, 13, 1, 100] : step 1: rotating to the right to produce 99, 1-100 and spin to the right step 2: [13, 3-1-100]Copy the code

prompt

  • 1 <= nums.length <= 2 * 10^4
  • -2^31 <= nums[i] <= 2^31 - 1
  • 0 <= k <= 10^5

Their thinking

The array to flip

For the range of elements that need to be moved, we can discard multiples that exceed the length of the array and just take the remainder, thus eliminating some meaningless loops.

When we move the elements to the right k times, we move k elements in the tail to the head of the array, and we move the elements in the head back k positions. Then we can first reverse the whole array, so that the tail element moves to the head, and the elements in the head move to the tail. After the reversal is completed, the final result can be obtained by reversing each element with k as the separation point.

class Solution {
    public void rotate(int[] nums, int k) {
        int n = nums.length;
        // Remove the number of extra steps
        k %= n;
        
        // the whole thing is flipped
        reverse(nums, 0, n - 1);
        // Invert to get k elements beyond the boundary after being moved back
        reverse(nums, 0, k - 1);
        // Invert to get the element moved k bits back
        reverse(nums, k, n - 1);
    }

    /** * reverses the array */
    public void reverse(int[] nums, int left, int right){
        while(left < right){ nums[left] = nums[left] + nums[right] - (nums[right--] = nums[left++]); }}}Copy the code

Complexity analysis

  • Time complexity: O(N)O(N)O(N)
  • Space complexity: O(1)O(1)O(1)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/ro…