Shulou(Shulou.com)06/01 Report--

Today, the editor will share with you the relevant knowledge points about how to solve the C language rotation array problem. The content is detailed and the logic is clear. I believe most people still know too much about this knowledge, so share this article for your reference. I hope you can get something after reading this article, let's take a look at it.

Topic description

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

Example

1. Example 1

Input: 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。 Example 2

Input: nums = [- 1jue 100jue 3jue 99], k = 2

Output: [3, 99, 99, 14, 1, 100]

Explanation:

Turn one step to the right: [99mmei 1mai 100jue 3]

Turn 2 steps to the right: [3, 99, 99, 1, 100]

Problem-solving ideas

In order to make the space complexity of the algorithm O (1) and rotate in place, no additional array can be created.

Take example 1 as an example. Use the triple inversion method to rotate the array k times

First, the whole reversal becomes (7, 6, 5, 4, 3, 2, 1)

The inverse rotor array [0, k-1] becomes (5, 6, 7, 4, 3, 2, 1)

The inverse rotor array [k, numsSize-1] becomes (5, 6, 7, 1, 2, 3, 4)

1. Reverse as a whole first

Set two pointer variables to point to the head and tail, respectively. When begin numsSize) {k% = numsSize;} code

This code takes the main function. The LeetCode topic is the interface type without the main function. Because you have to rotate three times. So write the while loop as a function to facilitate reuse.

LeetCode189. Rotation array # includevoid rotate1 (int* begin, int* end) {while (begin)

< end) { int t = 0; t = *begin; *begin = *end; *end = t; ++begin; --end; }}void rotate(int* nums, int numsSize, int k) { //假如右旋10个数，先旋7个后又回到了原来的样子。然后再旋3次的话和本题再旋3次一模一样。 if (k >

NumsSize) {k% = numsSize;} int* begin = nums; int* end = nums + numsSize-1; rotate1 (begin, end); rotate1 (begin, begin+k-1); rotate1 (begin+k, end);} int main () {int nums [] = {1Med 2Ling 3Ling 5J 6J 7}; int sz = sizeof (nums) / sizeof (nums [0]) Rotate (nums, sz, 3); for (int I = 0; I < sz; iTunes +) {printf ("% d", nums [I]);} return 0;} above is all the content of the article "how to solve the problem of C language rotation array". Thank you for reading! I believe you will gain a lot after reading this article. The editor will update different knowledge for you every day. If you want to learn more knowledge, please pay attention to the industry information channel.

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.