title: 【每日一题】LeetCode 154.寻找旋转排序数组中的最小值 II
tags:

  • leetcode
  • acwing
  • 每日一题
    abbrlink: b04e1ac
    date: 2021-04-09 10:12:49

LeetCode 154.寻找旋转排序数组中的最小值 II

思路

这道题和前两天的每日一题解法基本一致，就是无论怎样旋转，他在一个分界点前后分别都是单调递增的，而这个分界点就是整个数组的最小值，如图

【每日一题】LeetCode-154-寻找旋转排序数组中的最小值-II - 图1

其中，最右侧的平行部分的数与最左边平行数相同，这部分不满足二分性质，因此需要去掉（或者加一条相同数取较小序号应该也可以执行，可以自行尝试下）因此，只需要通过二分法找到这个最小分界点即可，为了避免对边界情况的处理，可以在数组长度较小的时候直接线性扫描出最小值（这里选择为5，可以自行调整）

C++代码

  1. class Solution {
  2. public:
  3.     int findMin(vector<int>& nums) {
  4.         int l=0, r=nums.size()-1;
  5.         while(l<r && nums[r]==nums[l])  r--;
  6.         if(r-l+1<5)
  7.         {
  8.             int res=INT_MAX;
  9.             for(int x : nums)   res=min(res,x);
  10.             return res;
  11.         }
  12.         if(nums[0]<=nums[r])    return nums[0];
  13.         else
  14.         {
  15.             while(l<r)
  16.             {
  17.                 int mid=(l+r+1)/2;
  18.                 if(nums[mid]>=nums[0])  l=mid;
  19.                 else r=mid-1;
  20.             }
  21.             return nums[r+1];
  22.         }
  23.     }
  24. };

AcWing 69.数组中数值和下标相等的元素

思路

性质:nums[i]-i >= nums[i-1]-(i-1)

由以上思路即可进行二分，由于题目只要求找到任意一个，所以不需要加任何条件限制，直接解出结果然后再单独对二分点进行判断即可

C++代码

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