平时一些基本的算法要牢记，要成为我们算法基础操作，这样解决问题时才能在基本操作的基础上举一反三。常用的基本操作如下：

      1）、reverse 基本操作具有O(n)的时间复杂度， O(n)的空间复杂度；

       2）、除此之外，二分搜索、快速排序、优先级队列、堆、平衡二叉搜索树、散列表的各项时间、空间复杂度，都是基本操作的例子，它们不仅对分析算法的复杂度有帮助，更在我们设计算法的时候起到重要的作用。

本期例题：LeetCode 189 - Rotate Array[1]（Easy）

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

下面将展示旋转数组的三种不同的解法。

解法1：使用额外空间

这是最普通的一种解法。我们可以使用一个辅助数组存储原数组末尾的 k 个数字，然后再移动剩下的数字。数字移动的过程如下所示。

使用辅助数组进行移动

这种解法的时间复杂度是 ，空间复杂度是 。很显然，它使用了额外的空间，还可以进一步优化。

解法2：环状替换

有些人首先想到的是这个思路。我们可以轻松推出每个数字最后应该在的位置，那么就可以一个一个地把它们放到正确的位置上。以 、 为例，移动的顺序是：1 ➝ 3 ➝ 5 ➝ 7 ➝ 2 ➝ 4 ➝ 6 ➝ 1。如下图所示，所有的箭头构成了一个环。

n=7, k=2 时的环状替换过程

那么我们的替换方法是：先用临时变量保存 1，将 6 放到 1 处，再将 4 放到 6 处…… 以此类推，最后将 1 放到 3 处。

不过，这种解法的正确性不容易证明。实际上，当  是   的倍数时，上面的这种替换方法并不成立。如下图所示，当 、 时，实际上存在两个环：

n=8, k=2 时的环状替换过程

* 1 ➝ 3 ➝ 5 ➝ 7 ➝ 1

* 2 ➝ 4 ➝ 6 ➝ 8 ➝ 2

如果从 1 出发，将只能替换 1、3、5、7 四个数，还需要再从 2 出发一遍。可见这种思路在实现上也比较麻烦。虽然这种方法达到了  的时间复杂度和  的空间复杂度，但是由于证明和实现上的复杂，并不推荐。

解法3：reverse 操作

可能你已经知道了 reverse 操作的解法，如果你还不知道的话，那么这个解法会让你恍然大悟，就像 Two Sum 问题的那个双指针解法一样。先将整个数组反转，再将数组的前后两半（前 k 个数和后 k 个数）分别反转，就可以实现数组的旋转了。

三次反转（reverse）操作的过程如下图所示：

三次反转操作的过程

相应的代码如下，非常简单明了。这个解法容易理解、容易证明、容易记忆，又能达到最好的  时间、 空间，可以说是最完美的解法。

public void rotate(int[] nums, int k) {

    int N = nums.length;

    k %= N;

    reverse(nums, 0, N);

    reverse(nums, 0, k);

    reverse(nums, k, N);

}

void reverse(int[] nums, int begin, int end) {

    for (int i = begin, j = end - 1; i < j; i++, j--) {

        int temp = nums[i];

        nums[i] = nums[j];

        nums[j] = temp;

    }

}

reverse 操作的更多应用

旋转数组有一道推广题目，反转单词：LeetCode 151 - Reverse Words in a String[4]（Medium）

将字符串中的单词顺序进行反转。例如：

* 输入："the sky is blue"

* 输出："blue is sky the"

另外，reverse 操作还可以用在一些字符串和数字转化的题目中。例如：

* LeetCode 415 - Add Strings[5]（Easy）

计算两个字符串形式的非负整数的和。

* LeetCode 504 - Base 7[6]（Easy）

给定一个整数，将其转化为7进制，并以字符串形式输出。

无论是做加法还是进制转换，都是先计算结果的低位数字，再到高位数字。而输出的是字符串形式，这意味着要不断在字符串的开头插入字符，时间开销很大。

一种解决方法是使用数组或栈来临时保存结果的每一位数字，最后再输出成字符串。当然还有另一个更简单的方法：直接输出一个“反着的”结果字符串，最后再将字符串反转即可。

总结

“容易想出解题思路”和“容易写出实现代码”其实是相辅相成的。因为代码实际上就是思路在纸上的落实。我们在面试中，需要锻炼这种能在有限时间内写出正确的、bug-free 代码的能力。所以我们在做题的时候，需要重点掌握的不是那些最快速、最花哨的解法，而是思路最清晰、代码最简洁的解法。

本篇文章以 reverse 为例讲述了基本操作的重要作用，希望你能在做题的过程中总结出更多的基本操作。下篇文章是姊妹篇，将介绍“基本数据结构”的作用，敬请期待。