Given a

**rotated**sorted array, recover it to sorted array in-place.**Example**

**[4, 5, 1, 2, 3]**->

**[1, 2, 3, 4, 5]**

**Challenge**Expand

**Clarification**Expand

**Tags**Expand

**Solution:**

The key to the problem is to reverse the list. There are three steps. Take the example of [4, 5, 1, 2, 3].

Step 1: [4, 5] -> [5, 4]

Step 2: [1, 2, 3] -> [3, 2, 1]

Step 3: [5, 4, 3, 2, 1] -> [1, 2, 3, 4, 5]

**Code (Java):**

/** * Copyright: NineChapter * - Algorithm Course, Mock Interview, Interview Questions * - More details on: http://www.ninechapter.com/ */ import java.util.ArrayList; public class Solution { /** * @param nums: The rotated sorted array * @return: The recovered sorted array */ private void reverse(ArrayList<Integer> nums, int start, int end) { for (int i = start, j = end; i < j; i++, j--) { int temp = nums.get(i); nums.set(i, nums.get(j)); nums.set(j, temp); } } public void recoverRotatedSortedArray(ArrayList<Integer> nums) { for (int index = 0; index < nums.size() - 1; index++) { if (nums.get(index) > nums.get(index + 1)) { reverse(nums, 0, index); reverse(nums, index + 1, nums.size() - 1); reverse(nums, 0, nums.size() - 1); return; } } } }

## No comments:

## Post a Comment