C++面试宝典第18题：旋转数组

题目

        给定一个数组，将数组中的元素向右移动k个位置，其中k是非负数。要求如下：

        （1）尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。

        （2）使用时间复杂度为O(n)和空间复杂度为O(1)的原地算法解决这个问题。

        示例 1：

输入: [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]

        示例 2：

输入: [-8, -100, 50, 66] 和 k = 2
输出: [50, 66, -8, -100]
解释: 
向右旋转1步: [66, -8, -100, 50]
向右旋转2步: [50, 66, -8, -100]

解析

        这道题主要考察应聘者从多个角度、多个维度分析和思考问题的能力。

        最直接、最简单的解决方案当然是“暴力法”，也就是每次将数组向右移动一个元素，一共旋转k次。向右移动一个元素，需要将最后一个元素移动到数组开头，然后将其他元素依次右移。“暴力法”的