“Rotate sorted array”系列问题

本文主要是介绍“Rotate sorted array”系列问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个排序的数组，进行数组旋转之后引出了一系列的问题，这里将遇到的相关问题做一个总结，并给出解决方法，备用所需。

有序数组旋转操作

这个问题是所有系列问题的起始，给一个有序数组，使用这个操作进行旋转，得到的数组就可以以之为其他问题的基础进行引申。

Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

这个问题的解决思路有如下几个：
1. 单独申请一个数组，将下标间隔之后进行拷贝
2. 将前n-k个元素添加到后面，然后将前面的n-k个元素删除（利用vector的push_back和erase）
3. 进行原地操作，常数级的空间

上述思路的第三个比较巧妙，使用常数级的原地操作。代码如下：

void rotate(int* nums, int numsSize, int k) {int prev = numsSize > 0 ? nums[0] : 0, next = prev;int i = 0, j = 0;for(int n = 0; n < numsSize; ++n){i = (i + k) % numsSize;prev = next;next = nums[i];nums[i] = prev;if (i == j) //关键所在，如果出现重复，需要进行偏移操作{next = nums[++j];i++;}}
}

寻找最小值（无重复元素）

对于旋转过的有序数组，如果没有重复元素，那么依然可以利用有序性质来进行二分查找，来寻找元素，首先是寻找最小值。
这里假定数组的顺序是升序的，利用的原理依然是通过中间元素与首尾元素之间的关系。如果中间元素大于首元素，则从首元素到中间元素间（包含边界）都是有序的，无序部分在后一半区间，此时如果尾元素小于中间元素，则最小值在后半区间，否则在前半区间；如果中间元素小于首元素，则一定是尾部的较大元素被旋转到了头部，后半区间是有序的，最小值肯定在包括中间元素的前半区间。
上述思路的递归版本代码实现如下，时间复杂度是O(logN)。

    int findMin(vector<int>& nums) {return findMinHelper(nums, 0, nums.size() - 1);}int findMinHelper(vector<int> & a, int s, int e){if (s == e) return a[s];int m = (s + e) / 2;if (a[m] > a[s]){if (a[e] < a[m]) return findMinHelper(a, m + 1, e);else return findMinHelper(a, s, m);}else{return findMinHelper(a, s, m);}}

寻找最小值（有重复元素）

当存在重复元素时，需要考虑中间元素与首元素相等的情况：此时需要考虑两边，进行查找之后比较大小。其他情况类似。此时最差情况可能出现全部元素都相同，最差情况的复杂度为O(N)。

    ///递归版本int findMin(vector<int>& nums) {return findMinHelper(nums, 0, nums.size() - 1);}int findMinHelper(vector<int> & a, int s, int e){if (s == e) return a[s];int m = (s + e) / 2;if (a[m] == a[s]){int l = findMinHelper(a, s, m);int r = findMinHelper(a, m, e);return l > r ? r : l;}else if(a[m] > a[s]){if (a[e] < a[m]) return findMinHelper(a, m + 1, e);else return findMinHelper(a, s, m);}else{return findMinHelper(a, s, m);}}///非递归版本int findMin(vector<int> & nums){int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == nums[l]){if (nums[r] >= nums[m]) --r;else ++l;}else if (nums[m] > nums[l]){if (nums[r] < nums[m]) l = m + 1;else r = m;}else r = m;}return nums[l];}

查找指定元素（无重复元素）

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
You are given a target value to search. If found in the array return its index, otherwise return -1.

当没有重复元素时，套用前面的查找最小元素的思路即可：

int search(vector<int> & nums, int target)
{int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] > nums[l]){//target在前半区间，target可能等于首元素，故大于等于号不可少if (target < nums[m] && target >= nums[l]) r = m - 1;else l = m + 1;}else{//target在后半区间，target可能等于尾元素，大于等于号不可少if (target > nums[m] && target <= nums[r]) l = m + 1;else r = m - 1;}}if (l == r && nums[l] == target) return l;return -1;
}

查找指定元素（有重复元素）

套用前面的有重复元素查找最小元素的思路，针对相等的情况进行区别对待即可。下面为非递归版本，递归版本与前面类似。

    int search(vector<int> & nums, int target){int l = 0, r = nums.size() - 1;while(l < r){int m = l + (r - l) / 2;if (nums[m] == target) return m;if (nums[m] == nums[l]){if (nums[r] >= nums[m]) --r;else ++l;}else if (nums[m] > nums[l]){if (target >= nums[l] && target < nums[m]) r = m - 1;else l = m + 1;}else{if ( target > nums[m] && target <= nums[r]) l = m + 1;else r = m - 1;}}return nums[l];}