title: LeetCode.81-每日一题-搜索旋转排序数组 II
tags:

  • leetcode
  • 每日一题
    abbrlink: 2cf5b000
    date: 2021-04-07 15:04:50

LeetCode81 搜索旋转排序数组 II

本题分析到的最坏情况下的最好复杂度的解法均为线性解法，所以就拿线性解法做了，时间复杂度是O(n)

C++代码

  1. class Solution {
  2. public:
  3.     bool search(vector<int>& nums, int target) {
  4.         for(auto &v:nums)
  5.         {
  6.             if(v==target)
  7.                 return true;
  8.         }
  9.         return false;
  10.     }
  11. };

AcWing22 旋转数组的最小数字

除了最后水平的一段（黑色水平那段）之外，其余部分满足二分性质：竖直虚线左边的数满足nums[i]≥nums[0]；而竖直虚线右边的数不满足这个条件。
分界点就是整个数组的最小值。

所以我们先将最后水平的一段删除即可。

这里还有一段y总的特殊情况的tip

另外，不要忘记处理数组完全单调的特殊情况：

当我们删除最后水平的一段之后，如果剩下的最后一个数大于等于第一个数，则说明数组完全单调。

C++代码

  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int n=nums.size()-1;
  5.         if(n<0) return -1;
  6.         while(n>0 && nums[n] == nums[0])    n--;
  7.         if(nums[n]>=nums[0])    return nums[0];
  8.         int l=0, r=n;
  9.         while(l<r)
  10.         {
  11.             int mid=l+r>>1;
  12.             if(nums[mid] < nums[0]) r=mid;
  13.             else l=mid+1;
  14.         }
  15.         return nums[r];
  16.     }
  17. };