恢复翻转排序

题目

给定一个旋转排序数组,在原地恢复其排序。http://www.lintcode.com/zh-cn/problem/recover-rotated-sorted-array/

分析

这道题目其实是旋转字符串的逆命题。http://www.hoyt-tian.com/xuan-zhuan-zi-fu-chuan/
实现的方式也是一样的,通过反转实现恢复。

代码实现


public class Solution {
    void t(List nums, int start, int end){
        for(;start < end;start++,end--){
            Integer si = nums.get(start);
            Integer ei = nums.get(end);
            nums.set(start, ei);
            nums.set(end, si);
        }
    }
    /*
     * @param nums: An integer
     * @return: 
     */
    public void recoverRotatedSortedArray(List nums) {
        // write your code here
        if(nums.size() <= 1) return;
        int pos = -1;
        for(int i=1, last = nums.get(0); i < nums.size(); i++){
            int current = nums.get(i);
            if(last > current){
                pos = i;
                break;
            }
        }
        if(pos == -1) return;
        t(nums, 0, nums.size() - 1);
        t(nums, 0, nums.size() - pos - 1);
        t(nums, nums.size() - pos, nums.size() - 1);
    }
}

			
Show Comments

Get the latest posts delivered right to your inbox.