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]

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]

class Solution {
    void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    void reverse(vector<int> &num, int i, int j) {
        while(i < j) {
           swap(num, i, j);        
           i++;
           j--;
        }
    }
     
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int i = findMinPoint(nums);
        if (i == 0) return;
        reverse(nums, 0, i-1);
        reverse(nums, i, nums.size()-1);
        reverse(nums, 0, nums.size()-1);
    }
};

class Solution {
     void swap(vector<int> &num, int i, int j) {
        if (i != j) {
            int tmp = num[i];
            num[i]= num[j];
            num[j] = tmp;            
        }
    }
    int findMinPoint(vector<int> &A) {
       int l = 0, r = A.size()-1;
       
       if (A[l] < A[r]) return l;
       
       while(l < r) {
           int m = (l+r)/2;
           if (A[m] < A[r]) 
              r = m;
            else 
              l = m+1;
       }
       return r;
    }
    
public:
    void recoverRotatedSortedArray(vector<int> &nums) {
        int k = findMinPoint(nums);
        if (k == 0) return;
        
        int n = nums.size();
        int i = 0;
        int L = n;
        while(k > 0) {
            while(i+k <n) {
               swap(nums, i, i+k);
               i++;
            }
            
            int t = k;
            k = L%k? k - L%k : 0;
            L = t;
        }
    }
};