LintCode (39) Recover Rotated Array

Given a rotated sorted array, recover it to sorted array in-place.

Have you met this question in a real interview? 

Yes

Example

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

Challenge

In-place, O(1) extra space and O(n) time.

Clarification

What 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]

本来打算装一下，先做了上一题的findPeak， 再来做这题，因为这个题目要找出一个local minimum来。但是发现corner case太多了，因为上题保证有一个local peak,而且无重复数组， 这个就不行了。其实有recursion的办法来找最小的，但是stack上空间O(N), 而且由于三步反转法的原因，log(n)的搜索不改变o(n)的复杂度，老老实实的o(n)好了。。。

三步反转法就是翻转这种roated array, string用的，首先每段各自翻转，然后一起翻转，当然，也可以用这个来翻转有序的数组，原理一样，先全翻转再各自翻转。。。扯远了。。。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: // reverse each part then reverse the whole // for find min element, there is a corner case is num[beg]<num[end] // recursion has space o(n) on stack void recoverRotatedSortedArray(vector<int> &nums) { if (nums.size()<2 || nums[0]<nums[nums.size()-1]) return; int min_index=findMin(nums); reverse(nums, 0, min_index-1); reverse(nums, min_index, nums.size()-1); reverse(nums,0,nums.size()-1); } int findMin(vector<int>& nums){ int i=0; while(i<nums.size()-1 && nums[i]<=nums[i+1]) i++; return i+1; } void reverse(vector<int>& nums, int beg, int end){ while(beg<end){ swap(nums[beg++],nums[end--]); } } };