Location>code7788 >text

[Ninja Algorithm] Rotation from fan blade to array: Exploring the problem of rotating array | LeetCode 189 Rotation array

Popularity：649 ℃/2025-02-05 22:10:49

From fan blades to array rotation: Exploring the problem of rotating array rotation

Algorithms in life

Imagine you watching a fan rotate slowly, the distance between three blades at a time. The blade that was originally above turned to the right, and the blade that was originally on the right turned to the lower... This is a vivid rotation process. For example, if the kindergarten teacher asks the children to form a circle and shouts "Move 3 positions to the right", each child will go to a new position.

This kind of rotation can be seen everywhere in life: the rotation seat arrangement of restaurants, the rotation of duty tables, the rotation of supermarket products, and even the rotation system of farmland. They all embody the same rule: keep the original order and move a specific number of steps as a whole.

Problem description

LeetCode's question 189 "Rotation Array" is described as follows: Give you an array, rotate the elements in the array to the right by k positions, where k is a non-negative number.

For example:

Enter: nums = [1,2,3,4,5,6,7], K = 3
 Output: [5,6,7,1,2,3,4]
 explain:
 Rotate to the right 1 step: [7,1,2,3,4,5,6]
 Rotate to the right 2 steps: [6,7,1,2,3,4,5]
 Rotate to the right 3 steps: [5,6,7,1,2,3,4]

The most intuitive solution: temporary array

Just like when children rotate their positions, they first stand in the new position and then sit down. We can record the new position of each element with a temporary array.

Let's use a simple example to understand:

Original array: [1,2,3,4], k = 2
 1. Create a temporary array: [0,0,0,0]
 2. 1 should be moved to position (0+2)%4=2: [0,0,1,0]
 3. 2 should be moved to position (1+2)%4=3: [0,0,1,2]
 4. 3 should move to position (2+2)%4=0: [3,0,1,2]
 5. 4 should be moved to position (3+2)%4=1: [3,4,1,2]
 6. Copy back to the original array: [3,4,1,2]

Optimization solution: three flips

A careful observation will reveal an interesting rule: if we divide the array into two parts, k elements on the right and other elements on the left, we can complete the rotation in just three steps:

  1. Flip the entire array
  2. Flip the first k elements
  3. Flip the elements behind

Just like the card-cutting technique when playing poker: first stack and reverse, and then adjust the order of the two stacks separately.

The principle of three flips

Dining table seating to understand:

  1. Everyone stands up, swap positions from left to right (overall flip)
  2. The first k person adjusts his relative position (the first k person flips)
  3. The rest of the people adjust their relative positions (the rest is flipped)

Example demonstration

Use nums = [1,2,3,4,5], k = 2 to illustrate:

Original array: [1,2,3,4,5]

 1. Overall flip:
 [1,2,3,4,5] -> [5,4,3,2,1]

 2. Flip the first k:
 [5,4,3,2,1] -> [4,5,3,2,1]

 3. Flip the remaining part:
 [4,5,3,2,1] -> [4,5,1,2,3]

Java code implementation

public void rotate(int[] nums, int k) {
     if (nums == null || <= 1) {
         Return;
     }
    
     // Handle k is greater than the array length
     k = k % ;
     if (k == 0) return;
    
     // 1. Flip the entire array
     reverse(nums, 0, - 1);
    
     // 2. Flip the first k elements
     reverse(nums, 0, k - 1);
    
     // 3. Flip the remaining elements
     reverse(nums, k, - 1);
 }

 private void reverse(int[] nums, int start, int end) {
     while (start < end) {
         // Exchange the beginning and end elements
         int temp = nums[start];
         nums[start] = nums[end];
         nums[end] = temp;
         start++;
         end--;
     }
 }

Solution comparison

Let's compare these two methods:

Temporary array method:

  • Time complexity: o (n)
  • Space complexity: O(n)
  • Advantages: Intuitive thinking, easy to understand
  • Disadvantages: Additional space is required

Three-time flip method:

  • Time complexity: o (n)
  • Space complexity: o (1)
  • Advantages: High space efficiency, simple implementation
  • Disadvantages: Not intuitive enough

Thinking inspiration

This question tells us:

  1. Sometimes intuitive solutions are not necessarily optimal
  2. Observing data rules is important
  3. The remaining calculation is useful when dealing with ring structures
  4. The flip operation can be used to change the element position relationship

Similar questions include:

  • Reverse string
  • String rotation
  • Implementation of circular queues

summary

Through the question of rotating arrays, we not only learned a classic array operation technique, but more importantly, we understand how to find an elegant solution by observing data characteristics. Remember, when you encounter a problem that needs to move the element position, consider whether the flip operation can help us!

Author: Ninja Algorithm
Official account: Ninja Algorithm

I have prepared a list of questions to practice and detailed questions for these questions, covering most common interview questions. I can say responsibly that as long as you truly master these questions, 80% of the algorithm interviews will encounter similar questions. Reply to the official account [Question List] to obtain ~

<Previous