lintcode：Recover Rotated Sorted Array恢复旋转排序数组

题目：

恢复旋转排序数组

给定一个旋转排序数组，在原地恢复其排序。

样例

[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]

解题：

开始我想，先找到中间的临界点，然后在排序，临界点找到了，排序不知道怎么搞了，在这里，看到了很好的方法，前半部分逆序，后半部分逆序，整体再继续。

Java程序：

public class Solution {
    /**
     * @param nums: The rotated sorted array
     * @return: void
     */
    public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
        // write your code
        int numslen = nums.size();
        int i=0;
        for(i=0;i<numslen-1;i++){
            if(nums.get(i)>nums.get(i+1)){
                reverse(nums,0,i);
                reverse(nums,i+1,numslen-1);
                reverse(nums,0,numslen-1);
            }
        }

    }
    public void reverse(ArrayList<Integer> nums,int start,int end){
        while(start<end){
            int tmp = nums.get(start);
            nums.set(start,nums.get(end));
            nums.set(end,tmp);
            start++;
            end--;
        }
    }
}

View Code

总耗时: 1414 ms

然后我看到网上用的都是这个方法。。。。

Python程序：

class Solution:
    """
    @param nums: The rotated sorted array
    @return: nothing
    """
    def recoverRotatedSortedArray(self, nums):
        # write your code here
        if nums==None:
            return
        numslen = len(nums)
        for index in range(numslen-1):
            if(nums[index]>nums[index+1]):
                self.reverse(nums,0,index)
                self.reverse(nums,index+1,numslen-1)
                self.reverse(nums,0,numslen-1)
                
    def reverse(self,nums,start,end):
        while start<end:
            self.swap(nums,start,end)
            start+=1
            end-=1
            
    def swap(self,nums,start,end):
        tmp = nums[start]
        nums[start] = nums[end]
        nums[end] = tmp

View Code

总耗时: 228 ms