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