给定一个旋转排序数组，在原地恢复其排序。
说明
什么是旋转数组？
比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
样例
[4, 5, 1, 2, 3]
->[1, 2, 3, 4, 5]
挑战
使用O(1)的额外空间和O(n)时间复杂度
代码
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: The recovered sorted array
*/
// reverse拥有 O(1) 的空间复杂度, O(n) 的时间复杂度
private void reverse(List<Integer> nums, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = nums.get(i);
// ArrayList.add()是将原来 index 上的对象向后移动
// ArrayList.set()是将原来 index 上的对象替换掉
nums.set(i, nums.get(j));
nums.set(j, temp);
}
}
// 三步翻转法
public void recoverRotatedSortedArray(List<Integer> nums) {
for (int index = 0; index < nums.size() - 1; index++) {
// 遍历数组找到排序变化的分界点
if (nums.get(index) > nums.get(index + 1)) {
reverse(nums, 0, index);
reverse(nums, index + 1, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
return;
}
}
}
}
本题要注意考虑没有旋转的特殊情况比如 123456，如果写成下面这样在特殊情况就会报错，找不到就不执行，如果写成这样会翻转 index 为 0 的结点
错误
