189. 轮转数组

发表于 分类于 Disqus： 本文字数： 956 阅读时长 ≈ 2 分钟

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3 输出: [5,6,7,1,2,3,4] 解释: 向右轮转 1 步: [7,1,2,3,4,5,6] 向右轮转 2 步: [6,7,1,2,3,4,5] 向右轮转 3 步: [5,6,7,1,2,3,4]

解：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if(nums.size()<2) return;
        k%=nums.size();
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+k);
        reverse(nums.begin()+k,nums.end());
    }
};

image-20220222185337166可以用辅助数组实现，原地处理的话就先整体旋转，前半部分旋转，后半部分旋转。

注意k很大的情况下先与数组长度取余可以得到确切移动的位数。

std::reverse函数：

在algorithm头文件中预定义。

Syntax:

1
2
3
void reverse(BidirectionalIterator first, BidirectionalIterator last)
BidirectionalIterator is an iterator that can be used to access any
elements of a container in both forward and backward direction.

Examples:

1
2
3
4
5
6
7
8
Input : 10 11 12 13 14 15 16 17
Output :10 11 12 13 14 17 16 15
Explanation:
reverse(v.begin() + 5, v.begin() + 8);
In the above function, input we have applied reverse() on the vector
from index 5 to index 7.
Therefore when we display the vector we get reverse order
from index 5 to index 7.

注意第二个参数要往后一位，也可以用v.end()