导航

题面解析 IAC代码解析 IIAC代码

题面

原题链接 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。 编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false

解析 I

本题可以使用二分法求解，思路和搜索排序数组I类似，但是需要处理一下重复元素，可以发现当处理掉重复元素后，本题转化为了搜索排序数组I，最坏情况下所有元素都相同，算法时间复杂度为$\mathcal{O}(n)$，理想情况下可以达到$\mathcal{O}(\log n)$

AC代码

class Solution { public: bool search(vector<int>& nums, int target) { if(nums.empty()) return false; int R = nums.size()-1; while(R>=0 && nums[R]==nums[0]) --R; //如果首尾元素相同，则进行数组截尾 if(R<0) return nums[0]==target; //如果所有数组元素都相同，进行判断 // 二分法, 定位出分界点 int l = 0, r=R; while(l<r){ int mid = l+r+1 >> 1; if(nums[mid]>=nums[0]) l=mid; else r=mid-1; } // 判断target应该位于哪一部分 if(target>=nums[0]) r=l, l=0; else l++, r=R; while(l<r){ int mid=l+r>>1; if(nums[mid]>=target) r=mid; else l=mid+1; } return nums[r]==target; } };

解析 II

在折断数组中随机定位一个点必然将数组分为有序部分和无序部分，分别考虑目标值是否出现在了数组的有序部分中，进行二分查找

AC代码

class Solution { public: bool search(vector<int>& nums, int target) { int l=0, r=nums.size(); while(l!=r){ int mid=l+(r-l)/2; if(nums[mid]==target) return true; // 前半部分为有序 if(nums[l]<nums[mid]){ // 判断目标值是否在该区间中 if(nums[l]<=target && target<nums[mid]) r=mid; else l=mid+1; } // 如果后半部分有序 else if(nums[l]>nums[mid]){ if(nums[mid]<target && target<=nums[r-1]) l=mid+1; else r=mid; } // 重复值 else ++l; } return false; } };