leetcode_rotate_array

发表于

难度：Easy

除了翻转之外的做法。使用cur纪录当前应该替换的数字。每次走k步，如果回到了初始位置，则＋1。总计走n步。

[1 2 3 4 5]    k=2
[1 2 3 4 5 6] k=2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        k = k % n;
        int i = 0;
        int start = i;
        int cur = nums[i];
        int count = 1;
        while(count++ <= n)
        {
            i = (i+k) % n;
            int temp = nums[i];
            nums[i] = cur;
            if(i == start)
            {
                i++;
                start++;
                cur = nums[i];
            }
            else
            {
                cur = temp;
            }
        }
    }
};
```	
运行结果：19ms，超过39.36%

----


写的简洁一些。

class Solution {
public:
void rotate(vector& nums, int k) {
k = k % nums.size();
reverse(nums,0,nums.size()-k-1);
reverse(nums,nums.size()-k,nums.size()-1);
reverse(nums,0,nums.size()-1);
}
void reverse(vector& nums, int left, int right)
{
while(left < right)
swap(nums[left++],nums[right–]);
}
};

1
2
3
4
5
6
7
8
9
10
运行结果：19ms，超过39.36%。

------
解题思路：

		先观察数组[1,2,3,4,5,6,7],k=3。结果[5,6,7,1,2,3,4]
		把数组分为两段[1,2,3,4],[5,6,7]
		再对这两段翻转[4,3,2,1],[7,6,5]
		再对整体翻转[5,6,7,1,2,3,4]。
代码如下：

class Solution {
public:
void rotate(vector& nums, int k) {
k = k % nums.size();
auto first_segment_begin_it = nums.begin();
auto first_segment_last_it = first_segment_begin_it + nums.size()-k -1;
auto second_segment_begin_it = first_segment_begin_it+nums.size()-k;
auto second_segment_last_it = first_segment_begin_it + nums.size()-1;
reverse_vec(first_segment_begin_it,first_segment_last_it);
reverse_vec(second_segment_begin_it,second_segment_last_it);
reverse_vec(first_segment_begin_it,second_segment_last_it);
}
void reverse_vec(vector::iterator first_it, vector::iterator last_it)
{
while(first_it < last_it)
{
swap(first_it,last_it);
first_it++;
last_it–;
}
}
};
```
结果：运行时间26ms，超过24.92%。