rotated-array-problem
这篇文章是四道旋转数组的合集，因为关联性非常强，我就不分开写了。关于旋转排序数组的问题总共有四道：
我将从易到难，依次讲解。
搜索旋转排序数组(无重复值)
0x1 题目详情
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 你可以假设数组中不存在重复的元素。 你的算法时间复杂度必须是 O(log n) 级别。
测试用例:
输入: nums = [4,5,6,7,0,1,2], target = 0 输出: 4
0x2 解题思路
思路1：
$O(N)$的算法就没什么好说了。仔细瞧瞧这道题，要在一个范围内找到一组值，且有一定的规则，那么可以考虑使用二分法查找，并且题目中也提醒了我们使用二分。
关键是怎么二分。如何决定该抛弃哪一部分呢？
因为数组中是没有重复元素的。可以发现，将数组一分为二时，肯定有一半是有序的。所以我们排除区间的原则就是：
如果nums[mid]==target,代表我们找到了目标元素，直接返回结果即可。
如果左边区间有序，那么我们就看target是否在左边区间，如果在左边区间，那么我们就排除右边区间，否则排除左边有序的区间。
如果右边区间有序，那么我们同样看target在不在右边区间，如果在，那么就排除左侧区间。否则排序右侧区间。
最后我们的指针可能处于两个地方：
不在索引区间之内，表示没有找到，直接返回-1.
在索引区间，还需要查看我们找到的数是否符合目标
思路2： 我刚开始想到的是一定能找到旋转点，这里找到的旋转点是一对数。找到以后，以旋转点为界，左右区间肯定是有序的。然后在这两个区间分别使用二分查找。虽然最后也能找到元素。但是有一个前提：一定在数组内存在旋转点。
但是其实旋转点并不一定在数组内。这种方法不方便推广旋转有序数组的题目。
0x3 代码实现
方法一: 这里采用二分法实现，时间复杂度为$(logN)$,排除不需要的区间得代码与上述的思路一致。
public int search(int[] nums, int target) {
if(nums== null || nums.length==0){
return -1;
}
int result=-1;
int left=0;
int right=nums.length;
//还是可以采取左闭右开的区间
while(left<right){
int mid=left+(right-left)/2;//下中
if(nums[mid]==target){
return mid;
}
else if(nums[left]<nums[mid]){
if(nums[left]<=target&&target<nums[mid]){
right=mid;
}
else{
left=mid+1;
}
}
//那就是右半部分有序
else{
//这里的right-1不会越界，因为越界的条件是
//right=0，而left>=0时，left>=right已经停止循环
if(nums[mid]<target&&target<=nums[right-1]){
left=mid+1;
}
else{
right=mid;
}
}
}
if(right<0 || right>=nums.length){
return -1;
}
return result=nums[right]==target?right:-1;
}方法二:
先找到旋转点，再在旋转点两侧分别二分查找目标值。时间复杂度虽然也为$(logN)$，但是还是比上面差点意思。
class Solution {
//二分搜索 排除法
public int search(int[] nums, int target) {
if(nums==null || nums.length==0){
return -1;
}
if(nums.length==1 && nums[0]!=target){
return -1;
}
//首要目标是找到转折点处的索引i,j
//这里用二分搜索就不使用左闭右开的区间了，不方便，
//但是中点还是可以按照左闭右开的方式求
int begin=0;
int end=nums.length-1;
int mid=0;
//当begin到end的距离为2时就代表我们找到了转折点
while(begin+1<end){
mid=begin+(end+1-begin)/2;
if(nums[begin]<nums[mid]){
begin=mid;
}
else{
end=mid;
}
}
int result=binarySearch(nums,0,begin+1,target);
result= result!=-1?result:binarySearch(nums,begin+1,nums.length,target);
return result;
}
//搜索区间为左闭右开
int binarySearch(int[] nums,int begin,int end,int target){
int result=-1;
while(begin<end){
int mid=begin+(end-begin)/2;
if(nums[mid]==target){
return mid;
}
else if(nums[mid]<target){
begin=mid+1;
}
else{
end=mid;
}
}
return result;
}
}利用二分法
搜索旋转排序数组(有重复值)
0x1 题目详情
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。
测试用例:
示例 1: 输入: nums = [2,5,6,0,0,1,2], target = 0 输出: true
0x2 解题思路
当数组有重复元素时，我们再将数组一分为二，就很难判定某个区间是否有序了。例如区间[4,4,4,2,4] 但是我们可以淘汰掉相同得元素啊，这样不就把问题转化成无重复元素的情况了么，这么简单得办法我愣是想不到，我真是服了。
0x3 代码实现
时间复杂度最坏为$O(N)$，因为当不停得需要使用++移动指针时，最差需要移动n-1次，即$O(N)$得复杂度。
但是一般情况下就是二分得复杂度$O(logN)$。
class Solution {
public boolean search(int[] nums, int target) {
if(nums== null || nums.length==0){
return false;
}
if(nums.length==0 && nums[0]!=target){
return false;
}
//还是采取左闭右开区间
int left=0;
int right=nums.length;
int mid=0;
while(left<right){
mid=left+(right-left)/2;
if(nums[mid]==target){
return true;
}
//至于是先淘汰左区间还是先淘汰右区间，我倒觉得无所谓
//淘汰掉左区间相同得元素
if(nums[left]==nums[mid]){
left++;
continue;
}
//淘汰右区间相同得元素
if(nums[mid]==nums[right-1]){
right--;
continue;
}
else if(nums[left]<nums[mid]){
if(nums[left]<=target && target<nums[mid]){
right=mid;
}
else{
left=mid+1;
}
}
else{
if(nums[mid]<target && target<=nums[right-1]){
left=mid+1;
}
else{
right=mid;
}
}
}
if(right<0 || right>=nums.length){
return false;
}
boolean result=nums[right]==target?true:false;
return result;
}
}搜索旋转排序数组的最小值(无重复值)
0x1 题目详情
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 你可以假设数组中不存在重复元素。
测试用例:
示例 1: 输入: [3,4,5,1,2] 输出: 1
0x2 解题思路
这道题的思路是我从解题区看到的，是对左闭右开区间的一种转换，实在是佩服。
首先数组中的元素是不重复的，所以我们仍能够找到一个完全升序的区间，而最小值只可能出现在一个长度为2的降序区间内(有一种特殊情况需要考虑，就是整个区间都是升序的，这个会在后面提到)，所以我们要做的就是排除完全升序的区间。那么我们是怎么判定完全升序的区间呢？是先判定左边还是先判定右边？
先思考下最小值可能出现的情况(mid为中间指针)：
最小值在左半部分,[6,7,1,2,3]:我们最小值正好在中间，我们需要抛弃右半区间，因为抛弃左边会丢失最小值,(其实这里还提供一个不正当的理由：因为我们要找的是最小值，所以我们肯定倾向于往左边找，所以优先选择保留左半部分)有如下关系： $nums[left]>num[mid],nums[mid]<nums[right]$
最小值在右半部分，[3,6,7,1,2]:最小值右半区间，应该丢弃左半区间。此时有如下关系： $nums[left]nums[right]$
特殊情况，[1,2,3,6,7]：旋转点不在数组内，可以我们应该丢弃右半区间。此时有如下关系： $nums[left]<nums[mid],nums[mid]<nums[right]$
所以我们只需关注右半部分，总结如下：
当$nums[mid]<nums[right]$时，丢弃右半区间
当$nums[mid]>nums[right]$时，丢弃左半区间
为什么不关注左半部分呢？因为情况比上面的复杂。比如$nums[left]<nums[mid]$时，我们不知道该抛弃哪一部分。
同理：如果我们想找最大值，那么就优先保留右半部分，道理是一样的。
0x3 代码实现
这里left与right指针更新的方式采用二分模板的更新方式，但是我们不能直接套二分模板，仍需要做出一点改变:这里的二分的区间我们需要采取左闭右闭的区间。这样每次取的中点就是上中了。
这里的个性化简直巧妙。
当数组中只有一个元素时，left和right肯定指向最小值
当数组中有两个元素时：
$nums[left]<nums[right]$时，$nums[left]=nums[mid]$,此时right会更新mid，指向最小值
$nums[left]>nums[right]$时，$nums[left]=nums[mid]$,此时right会更新mid+1，指向最小值
class Solution {
public int findMin(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
int left=0;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left)/2;
if(nums[mid]<nums[right]){
//这么做是因为即将排序的右侧有序区间中最左边可能就是最小值
//需要把他保留下来
right=mid;
}
else{
left=mid+1;
}
}
return nums[right];
}
}搜索旋转排序数组的最小值(有重复值)
0x1 题目详情
假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。 注意数组中可能存在重复的元素。
测试用例:
示例 1： 输入: [1,3,5] 输出: 1 示例 2： 输入: [2,2,2,0,1] 输出: 0
0x2 解题思路
这和没重复值查找最小值的唯一区别就是有了重复元素。由于我们只关注右半部分，所以只要遇到相同元素淘汰就完事了。
淘汰区间选择的标准和无重复元素的情况是一样的。
0x3 代码实现
class Solution {
public int findMin(int[] nums) {
if(nums==null || nums.length==0){
return 0;
}
if(nums.length==1){
return nums[0];
}
int left=0;
int right=nums.length-1;
while(left<right){
//淘汰掉相同元素
int mid=left+(right-left)/2;
if(nums[mid]==nums[right]){
right--;
continue;
}
if(nums[mid]>nums[right]){
left=mid+1;
}
else{
right=mid;
}
}
return nums[right];
}
}总结
这四道题目可以说是很好的练习了二分法的使用。
所以使用场景：
我们呢期望找一个数，且这个数有范围，并且我们能够通过某种规则淘汰调一部分的时候，就可以考虑使用二分法。使用二分不一样要严格保证数组是有序的。
思考方向：
首先我们应该进行分类讨论
然后思考在哪种情况下应该保留哪一部分
最后思考我们应该制定何种规则才能实现上述的区间淘汰方法
二分模板并不是能够完全适用，特殊的情况可以做一些适当的定制。
Last updated
Was this helpful?