给定一个旋转排序数组,在原地恢复其排序。
什么是旋转数组? 比如,原始数组为
[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]
遍历数组,首先找到当前数大于下一个数的位置,也就是样例中的 5,然后将数组开头的元素到 5 进行翻转,结果是 [5, 4, 1, 2, 3]
,然后将后面的元素进行翻转,结果是 [5, 4, 3, 2, 1]
,再将整个数组翻转,就得到了最终结果。
public class Solution {
/**
* @param nums: The rotated sorted array
* @return: The recovered sorted array
*/
public void recoverRotatedSortedArray(List<Integer> nums) {
for (int i = 0; i < nums.size() - 1; i++) {
if (nums.get(i) > nums.get(i + 1)) {
reverse(nums, 0, i);
reverse(nums, i + 1, nums.size() - 1);
reverse(nums, 0, nums.size() - 1);
return;
}
}
}
public void reverse(List<Integer> list, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
int temp = list.get(i);
list.set(i, list.get(j));
list.set(j, temp);
}
}
};