Leetcode daily practice - 189. Rotation array

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper leetcode 189. Rotation array

Let’s get it！

---

---

1. Topic analysis

Give you an array , Rotate the elements in the array to the right k A place , among k It is a non negative number .

Example 1：

Example 2：

2. Title diagram

Train of thought ： Right hand k Time , Move one... In turn

Suppose we want to put the array [1,2,3,4,5,6,7], Spin to the right 3 Time

The first 1 Step , Define a variable tmp Used to store the last element of the array 7;

The first 2 Step , Before array n-1 Move the value back ;

The first 3 Step , hold tmp The value of is placed in the first empty position ;

This completes a right rotation , So we are rotating to the right k Time , You get the final result .

The time complexity of this method is $O(N\ast K)$; The space complexity is $O(1)$;
 
When K % N be equal to N-1 when , The worst , Because the time complexity is $O(N^2)$;

Train of thought two ： Extra open array

This method is based on Space for time How to do it .

It's simple , Open up another array , Put it behind k Put elements into the new array front , Put the front n-k Put a new array Back .（n Is the number of elements in the array ）.

The time complexity of this method is $O(N)$, The space complexity is $O(N)$

Train of thought three ： Three times reverse

This method is very most ！, We can go through Three times reverse To solve , Or the following array

The first 1 Trip to , To the front of the array n - k An inverse , As shown in the figure

The first 2 Trip to , After the array k An inverse , As shown in the figure

The first 3 Trip to , And then put the array Global inversion , As shown in the figure

The time complexity of this method is $O(N)$, The space complexity is $O(1)$.

3. Algorithm design

We could write one Inversion function reverse To realize the main part

Code implementation

void reverse(int* nums, int left, int right) {
    
	while (left < right) {
    
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		++left;
		--right;
	}
}

4. Code implementation

We use inverse functions reverse Pay attention when transferring parameters ： The subscript of an array is from 0 At the beginning , such as ： front 10 The element is 0 To 9;

Because the first 1 Go ahead n - k Inversion , here n = 7,k = 3, Then it's about the front 4 An inverse , But the subscript of the array is from 0 At the beginning , That is to say, before 4 The subscript of an element is 0 To 3, As shown in the figure

The first 2 Trip to , After the array k An inverse , That is after 3 Elements are inverted , That is, from the subscript 4 To 6 Start reverse , As shown in the figure

The first 3 Trip to , Invert the entire array , As shown in the figure

But we should also pay attention to one problem , If k Exceeds the number of array elements , What shall I do? ？

such as ： An array is [ 1 2 3 4 5 ] ,k = 6 When , At this time, the number of array elements is 5, It requires right rotation 6 A place , If according to the above analysis , Before the first trip n - k Inversion , That is to say 5 - 6 An inverse , Is it right -1 An inverse position ？

Let's first look at rotating the array to the right 6 How about a position , As shown in the figure

Why ！ You will find that the final result is Rotate right 1 A place Did you? ？

At this point, we should remember that the core of this problem is Rotation array , That is, when the number of rotations exceeds the length of the array , It's a new round ！

So we can start with k Remainder , And then rotate again ; For example, the array length is 8, I want to rotate to the right 10 Time , In fact, it turns to the right 2 Time , that 10 % 2 The result is 2 Do you ？

therefore , If k Greater than array length , So first of all k Remainder , And then rotate again , This will not affect the final result ！

Interface code

void reverse(int* nums, int left, int right) {
    
	while (left < right) {
    
		int tmp = nums[left];
		nums[left] = nums[right];
		nums[right] = tmp;
		++left;
		--right;
	}
}

void rotate(int* nums, int numsSize, int k) {
    
    k %= numsSize; //  If k Greater than array length , First pair k Remainder 
	reverse(nums, 0, numsSize - k - 1);
	reverse(nums, numsSize - k, numsSize - 1);
	reverse(nums, 0, numsSize - 1);
}

Submit results