39 恢复旋转字符串

原题网址： http://www.lintcode.com/zh-cn/problem/recover-rotated-sorted-array/#

给定一个旋转排序数组，在原地恢复其排序。

您在真实的面试中是否遇到过这个题？

Yes

说明

什么是旋转数组？

比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

样例

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

挑战

使用O(1)的额外空间和O(n)时间复杂度

 1 #include <iostream>
 2 #include <vector>
 3 #include <math.h>
 4 #include <string>
 5 #include <algorithm>
 6 using namespace std;
 7 
 8 //方法一;
 9  void recoverRotatedSortedArray1(vector<int> &nums)
10  {
11      int size=nums.size();
12      vector<int>::iterator minValue=min_element(nums.begin(),nums.end());
13      int index=distance(nums.begin(),minValue);
14      //cout<<index<<endl;
15      if (index!=0)
16      {
17          vector<int> temp(nums);
18          int k=0;
19          for (int j=index;j<size;j++)
20          {
21              nums[k++]=temp[j];
22          }
23          for (int i=0;i<index;i++)
24          {
25              nums[size-index+i]=temp[i];
26          }
27      }     
28  }
29 
30  //方法二;
31  void recoverRotatedSortedArray2(vector<int> &nums)
32  {
33      sort(nums.begin(),nums.end());
34  }
35 
36  //方法三-网;
37  void recoverRotatedSortedArray3(vector<int> &nums)
38  {
39      int size=nums.size();
40      vector<int>::iterator minValue=min_element(nums.begin(),nums.end());
41      int index=distance(nums.begin(),minValue);
42      
43      if (index!=0)
44      {
45          for (int i=0;i<index;i++)
46          {
47              nums.push_back(nums[i]);
48              //nums[size+i]=nums[i]; 上一行代码写成这样的赋值则出错，下标法访问vector数组不应超出界限;
49          }
50          int k=0;
51          for (int j=index;j<index+size;j++)
52          {
53              nums[k++]=nums[j];
54          } 
55          for (int i=size;i<index+size;i++)
56          {
57              nums.pop_back();
58          }
59      }     
60  }
61 
62  //方法4-网;
63  void rotateArray(vector<int> &a, int begin,int end);
64  void recoverRotatedSortedArray4(vector<int> &nums)
65  {
66      int size=nums.size();
77 
78      int ValueIndex=1;
79      for (;ValueIndex<size&&nums[ValueIndex-1]<=nums[ValueIndex];ValueIndex++) ;//循环体为空，找出最小元素索引;
80      if (ValueIndex!=1)                                    //注意此处等号不可少;
81      {
82          rotateArray(nums,0,ValueIndex-1);
83          rotateArray(nums,ValueIndex,size-1);
84          rotateArray(nums,0,size-1);
85      }
86  }
87 
88  void rotateArray(vector<int> &a, int begin,int end)
89  {
90      for (int i=begin,j=end;i<j;i++,j--)
91      {
92          swap(a[i],a[j]);
93      }
94  }

参考：

1 https://blog.csdn.net/github_34248245/article/details/50900004

2 https://www.cnblogs.com/libaoquan/p/7076858.html

3 https://www.cnblogs.com/sylz/p/5690418.html