你的位置:首页 > Java教程

[Java教程]Lintcode: Recover Rotated Sorted Array


Given a rotated sorted array, recover it to sorted array in-place.Example[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]ChallengeIn-place, O(1) extra space and O(n) time.ClarificationWhat is rotated array:  - For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

我的做法是先扫描不是ascending order的两个点,然后reverse array三次,分别是(0, i), (i+1, num.length-1), (0, num.length-1)

 1 public class Solution { 2   /** 3    * @param nums: The rotated sorted array 4    * @return: The recovered sorted array 5   */ 6   public void recoverRotatedSortedArray(ArrayList<Integer> nums) { 7     // write your code 8     if (nums==null || nums.size()==0 || nums.size()==1) return; 9     int i = 0;10     for (i=0; i<nums.size()-1; i++) {11       if (nums.get(i) > nums.get(i+1)) break;12     }13     if (i == nums.size()-1) return;14     reverse(nums, 0, i);15     reverse(nums, i+1, nums.size()-1);16     reverse(nums, 0, nums.size()-1);17   }18   19   public void reverse(ArrayList<Integer> nums, int l, int r) {20     while (l < r) {21       int temp = nums.get(l);22       nums.set(l, nums.get(r));23       nums.set(r, temp);24       l++;25       r--;26     }27   }28 }