【題目描述】
Given a rotated sorted array, recover it to sorted array in-place.
給定一個旋轉(zhuǎn)排序數(shù)組，在原地恢復其排序。
【題目鏈接】
http://www.lintcode.com/en/problem/recover-rotated-sorted-array/
【題目解析】
首先可以想到逐步移位，但是這種方法顯然太浪費時間，不可取。下面介紹利器『三步翻轉(zhuǎn)法』，以[4, 5, 1, 2, 3]為例。
首先找到分割點5和1
翻轉(zhuǎn)前半部分4, 5為5, 4，后半部分1, 2, 3翻轉(zhuǎn)為3, 2, 1。整個數(shù)組目前變?yōu)閇5, 4, 3, 2, 1]
最后整體翻轉(zhuǎn)即可得[1, 2, 3, 4, 5]
由以上3個步驟可知其核心為『翻轉(zhuǎn)』的in-place實現(xiàn)。使用兩個指針，一個指頭，一個指尾，使用for循環(huán)移位交換即可。
【參考答案】
http://www.jiuzhang.com/solutions/recover-rotated-sorted-array/
