恢复反转的有序数组

算法描述

给定一个翻转过的有序数组，输出原来的有序数组，例： [3, 4, 5, 1, 2] --> [1, 2, 3, 4, 5], [5, 6, 1, 2, 3, 4] --> [1, 2, 3, 4, 5, 6]

解题思路

找到数组翻转的位置，发现左右两边的数组都是有序的，把左右两边的数组逆序得到了一个逆序的数组，再把该数组逆序即可得到升序的数组

代码

public class Solution {
    /**
     * @param nums: An integer array
     * @return: nothing
     */
    public void recoverRotatedSortedArray(List<Integer> nums) {
        // write your code here
        int n = nums.size();
        List<Integer> result = new ArrayList();
        if (n <= 0) return; 
          // 找到逆序的位置
          int i = 0;
        for (i = 0; i < n - 1; i++) {
            // 
            if(nums.get(i) > nums.get(i+1)) {
                break;
            }
        } 
        if (i == (n - 1)) {
            result = nums;
        }
        else {
             result = reverseNums(nums, 0, i);
             result = reverseNums(nums, i + 1, n - 1);
             result = reverseNums(nums, 0, n - 1);
        }
        System.out.println(result);
    }
    
    public List<Integer> reverseNums(List<Integer> nums, int low, int high) {
        while(low < high) {
            int temp = nums.get(low);
            nums.set(low, nums.get(high));
            nums.set(high, temp);
            low++;
            high--;
        }
        return nums;
    }
}

总结

该思想也可以用于字符串、句子的翻转，对每一个组成部分逆序然后再整体逆序。