平時一些基本的算法要牢記谚殊，要成為我們算法基礎操作丧鸯，這樣解決問題時才能在基本操作的基礎上舉一反三嫩絮。常用的基本操作如下：

? ? ? 1）丛肢、reverse 基本操作具有O(n)的時間復雜度剿干， O(n)的空間復雜度蜂怎；

? ? ? ?2）怨愤、除此之外派敷，二分搜索撰洗、快速排序篮愉、優(yōu)先級隊列、堆试躏、平衡二叉搜索樹、散列表的各項時間设褐、空間復雜度泣刹，都是基本操作的例子，它們不僅對分析算法的復雜度有幫助椅您，更在我們設計算法的時候起到重要的作用。

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

給定一個數(shù)組寡键，將數(shù)組中的元素向右移動 k 個位置，其中 k 是非負數(shù)西轩。

下面將展示旋轉(zhuǎn)數(shù)組的三種不同的解法。

解法1：使用額外空間

這是最普通的一種解法藕畔。我們可以使用一個輔助數(shù)組存儲原數(shù)組末尾的 k 個數(shù)字马僻，然后再移動剩下的數(shù)字注服。數(shù)字移動的過程如下所示韭邓。

使用輔助數(shù)組進行移動

這種解法的時間復雜度是?溶弟，空間復雜度是?仍秤。很顯然可很，它使用了額外的空間，還可以進一步優(yōu)化凰浮。

解法2：環(huán)狀替換

有些人首先想到的是這個思路。我們可以輕松推出每個數(shù)字最后應該在的位置袜茧，那么就可以一個一個地把它們放到正確的位置上。以?笛厦、 為例纳鼎，移動的順序是：1 ? 3 ? 5 ? 7 ? 2 ? 4 ? 6 ? 1裳凸。如下圖所示贱鄙，所有的箭頭構(gòu)成了一個環(huán)姨谷。

n=7, k=2 時的環(huán)狀替換過程

那么我們的替換方法是：先用臨時變量保存 1逗宁，將 6 放到 1 處梦湘，再將 4 放到 6 處…… 以此類推瞎颗，最后將 1 放到 3 處。

不過哼拔，這種解法的正確性不容易證明引有。實際上倦逐，當? 是? ?的倍數(shù)時譬正，上面的這種替換方法并不成立僻孝。如下圖所示导帝，當?穿铆、 時您单，實際上存在兩個環(huán)：

n=8, k=2 時的環(huán)狀替換過程

* 1 ? 3 ? 5 ? 7 ? 1

* 2 ? 4 ? 6 ? 8 ? 2

如果從 1 出發(fā)荞雏，將只能替換 1虐秦、3凤优、5悦陋、7 四個數(shù)筑辨，還需要再從 2 出發(fā)一遍俺驶。可見這種思路在實現(xiàn)上也比較麻煩暮现。雖然這種方法達到了? 的時間復雜度和? 的空間復雜度，但是由于證明和實現(xiàn)上的復雜楚昭，并不推薦。

解法3：reverse 操作

可能你已經(jīng)知道了 reverse 操作的解法抚太，如果你還不知道的話，那么這個解法會讓你恍然大悟尿贫，就像 Two Sum 問題的那個雙指針解法一樣电媳。先將整個數(shù)組反轉(zhuǎn)帅霜，再將數(shù)組的前后兩半（前 k 個數(shù)和后 k 個數(shù)）分別反轉(zhuǎn)匆背，就可以實現(xiàn)數(shù)組的旋轉(zhuǎn)了身冀。

三次反轉(zhuǎn)（reverse）操作的過程如下圖所示：

三次反轉(zhuǎn)操作的過程

相應的代碼如下钝尸，非常簡單明了。這個解法容易理解珍促、容易證明铃辖、容易記憶猪叙，又能達到最好的? 時間娇斩、 空間穴翩，可以說是最完美的解法犬第。

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 操作的更多應用

旋轉(zhuǎn)數(shù)組有一道推廣題目芒帕，反轉(zhuǎn)單詞：LeetCode 151 - Reverse Words in a String[4]（Medium）

將字符串中的單詞順序進行反轉(zhuǎn)。例如：

* 輸入："the sky is blue"

* 輸出："blue is sky the"

另外背蟆，reverse 操作還可以用在一些字符串和數(shù)字轉(zhuǎn)化的題目中鉴分。例如：

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

計算兩個字符串形式的非負整數(shù)的和带膀。

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

給定一個整數(shù)志珍，將其轉(zhuǎn)化為7進制垛叨，并以字符串形式輸出伦糯。

無論是做加法還是進制轉(zhuǎn)換嗽元，都是先計算結(jié)果的低位數(shù)字舔株，再到高位數(shù)字还棱。而輸出的是字符串形式，這意味著要不斷在字符串的開頭插入字符惭等，時間開銷很大。

一種解決方法是使用數(shù)組或棧來臨時保存結(jié)果的每一位數(shù)字辞做，最后再輸出成字符串琳要。當然還有另一個更簡單的方法：直接輸出一個“反著的”結(jié)果字符串秤茅，最后再將字符串反轉(zhuǎn)即可稚补。

總結(jié)

“容易想出解題思路”和“容易寫出實現(xiàn)代碼”其實是相輔相成的框喳。因為代碼實際上就是思路在紙上的落實课幕。我們在面試中，需要鍛煉這種能在有限時間內(nèi)寫出正確的乍惊、bug-free 代碼的能力。所以我們在做題的時候润绎，需要重點掌握的不是那些最快速撬碟、最花哨的解法莉撇，而是思路最清晰呢蛤、代碼最簡潔的解法棍郎。

本篇文章以 reverse 為例講述了基本操作的重要作用其障，希望你能在做題的過程中總結(jié)出更多的基本操作坝撑。下篇文章是姊妹篇静秆，將介紹“基本數(shù)據(jù)結(jié)構(gòu)”的作用，敬請期待抚笔。