image.png
用三段翻转法！！！
如[4,5,1,2,3],首先[5,4],然后[3,2,1],最后[1,2,3,4,5]
class Solution {
public:
/**
* @param nums: An integer array
* @return: nothing
*/
void recoverRotatedSortedArray(vector<int> &nums) {
// write your code here
int index = 0;
int cur = 0;
for(int i = 1; i < nums.size(); i++){
if(nums[i] < nums[i-1]){
index = i;
}
}
int left;
int right;
left = 0, right = index - 1;
while(right >= left){
int tmp = nums[left];
nums[left++] = nums[right];
nums[right--] = tmp;
}
left = index, right = nums.size() - 1;
while(right >= left){
int tmp = nums[left];
nums[left++] = nums[right];
nums[right--] = tmp;
}
left = 0, right = nums.size() - 1;
while(right >= left){
int tmp = nums[left];
nums[left++] = nums[right];
nums[right--] = tmp;
}
}
};
