给定一个旋转排序数组，在原地恢复其排序。
[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]
使用O(1)的额外空间和O(n)时间复杂度
什么是旋转数组？
比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]
解题思路：这个就是找到第一个出现降序的位置，然后排序，如何利用O(1)的空间？举个例子，比如[4,5,1,2,3]，我们可以先将[4,5]颠倒为[5,4]，然后再将[1,2,3]颠倒[3,2,1]，之后再整个颠倒就整好是按照升序排列的;
1 public class Solution { 2 /** 3 * @param nums: The rotated sorted array 4 * @return: void 5 */ 6 public void reverse(ArrayList<Integer> nums,int start,int end){ 7 for(int i=start,j=end;i<j;i++,j--){ 8 int temp = nums.get(i); 9 nums.set(i,nums.get(j)); 10 nums.set(j,temp); 11 } 12 } 13 public void recoverRotatedSortedArray(ArrayList<Integer> nums) { 14 // write your code 15 for(int i=0;i<nums.size()-1;i++){ 16 if(nums.get(i)>nums.get(i+1)){ 17 reverse(nums,i+1,nums.size()-1); 18 reverse(nums,0,i); 19 reverse(nums,0,nums.size()-1); 20 } 21 } 22 return ; 23 } 24 }
原文：http://www.cnblogs.com/wangnanabuaa/p/5011706.html