lintcode-39. Recover Rotated Sorted Array

1. 问题描述

2. my solution

2.1 我的思路

1. 遍历数组, 找到分割数组的位置(前数字比后数字小)
2. 根据分割数组的位置来存放数据

时间复杂度为O(n)

2.2 代码实现

class Solution {
public:
    /**
     * @param nums: An integer array
     * @return: nothing
     */
    void recoverRotatedSortedArray(vector<int> &nums) {
        // write your code here
        vector<int> res(nums.size());
        
        int k = 0;
        int r = 0;
        for (int i = 0; i<nums.size()-1;  i++) 
        {
            if(nums[i] > nums[i+1])
            {
                 k = i;
                 break;
            }
        }
        if(k ==0) return;
        
        
        for(int i = k+1 ;i<nums.size();i++)
        {
                res[r++] = nums[i];
        }
        for(int i = 0 ; i<k+1;i++){
            res[r++] = nums[i];
        }
        nums = res;
    }
};

2.3 运行结果

3. others solutions

3.1 思路一