Shulou(Shulou.com)05/31 Report--

This article mainly explains "how to solve the problem of rotational array in C language". Interested friends may wish to take a look. The method introduced in this paper is simple, fast and practical. Let's let the editor take you to learn "how to solve the problem of rotational array in C language".

Topic 1. Topic description

Give you an array and rotate the elements in the array to the right, where k is a non-negative number.

Example 1:

Enter:

Nums = [1, 2, 3, 4, 5, 6, 7], k = 3

Output:

[5,6,7,1,2,3,4]

Explanation:

Turn one step to the right: [7, 1, 2, 3, 4, 5, 6]

Turn 2 steps to the right: [6, 7, 1, 2, 3, 4, 5]

Turn 3 steps to the right: [5, 6, 7, 1, 2, 3, 4]

two。 Request

Advanced:

Come up with as many solutions as possible, and there are at least three different ways to solve the problem.

Can you use an in-place algorithm with a space complexity of O (1) to solve this problem?

3. Original title link

one hundred and eighty nine。 Rotation array-LeetCode (leetcode-cn.com)

Second, related knowledge points

This topic actually involves the problem of complexity, including time complexity and space complexity.

Third, the method of thinking rotation

The best idea, which requires us to have a better understanding, the array can be divided into three parts.

Suppose we need to select k numbers:

1. The last k numbers are reversed.

two。 The first nmurk numbers are inverted.

3. Overall inversion

This method is the optimal method. Meet the requirements of the topic

Take example 1 as an example to illustrate:

1 2 3 4 5 6 7 stroke / rotate 3 digits

1 2 3 4 7 6 5 beat / last k digits upside down

4 3 2 1 7 6 5 pound / former nmurk digits inverted

5 6 7 1 2 3 4 stroke / overall inversion

The source code is as follows:

Void reverse (int*nums,int left,int right) {while (left=0;--end) {nums [end+1] = nums [end];} nums [0] = tmp;}}

Unfortunately, the space of this algorithm is so complex that it can not run through it and times out. The running result diagram is given.

Space for time

It is common to trade space for time, which is to open up an additional array, store selected numbers, and then store the previous data in the second half of the array. Finally, copy the new array to the original array.

The code is as follows

Void rotate (int* nums, int numsSize, int k) {k% = numsSize; int* newnum = (int*) malloc (sizeof (int) * numsSize); int j = 0; for (int I = numsSize-k;i)

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.