溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
【題目描述】
Given a rotated sorted array, recover it to sorted array in-place.
給定一個旋轉排序數組，在原地恢復其排序。
【題目鏈接】
http://www.lintcode.com/en/problem/recover-rotated-sorted-array/
【題目解析】
首先可以想到逐步移位，但是這種方法顯然太浪費時間，不可取。下面介紹利器『三步翻轉法』，以[4, 5, 1, 2, 3]為例。
首先找到分割點5和1
翻轉前半部分4, 5為5, 4，后半部分1, 2, 3翻轉為3, 2, 1。整個數組目前變?yōu)閇5, 4, 3, 2, 1]
最后整體翻轉即可得[1, 2, 3, 4, 5]
由以上3個步驟可知其核心為『翻轉』的in-place實現。使用兩個指針，一個指頭，一個指尾，使用for循環(huán)移位交換即可。
【參考答案】
http://www.jiuzhang.com/solutions/recover-rotated-sorted-array/
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
