题解 | #旋转数组的最小数字# 【左闭右开】【左闭右闭】

https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba

@[toc]

题目描述

153. 寻找旋转排序数组中的最小值

解题思路

需要注意的是mid始终有可能是最小值。我们在二分过程中,不能排除 Mid是最小值的可能性。

注意点:中位位置是 ==左中位==

两种base case

一个元素(奇数)

例如数组 [3] 。此时mid和right(or right-1)重合,应指向3

两个元素(偶数)

例如数据 [4,3]。此时mid应指向4,right(or right-1)指向3。即mid指向==左中位==。

左闭右开

此时

  • base case => 两个元素
  • 中位位置 => 左中位
    class Solution {
    public:
      int minNumberInRotateArray(vector<int> rotateArray) {
          vector<int>& nums = rotateArray;
          int n = nums.size();
          int left=0, right = n;    // init interval [0, n)
          while(left<right) {
              int mid = left+(right-1-left)/2;
              if(nums[mid]<nums[right-1]) {
                  right = mid+1;  // 区间shrink to [left, mid+1)。 此处不可排除mid,mid仍有可能是最小值
              } else  if(nums[mid]>nums[right-1]) {
                  left = mid+1;   // 区间shrink to [mid+1, right).
              } else  if(nums[mid]==nums[right-1]) {
                  right--;        // 区间shrink to [left, right-1)
              }
          }
          return nums[left];
      }
    };

左闭右闭

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        vector<int>& nums = rotateArray;
        int n = nums.size();
        int left=0, right = n-1;  // init interval [0, n-1]
        while(left<right-1) {
            int mid = left+(right-left)/2;
            if(nums[mid]<nums[right]) {
                right = mid;    // interval shrink to [left, mid]. mid is possible to be the least. 
            } else  if(nums[mid]>nums[right]) {
                left = mid+1;   //  interval shrink to [mid+1, right]
            } else  if(nums[mid]==nums[right]) {
                right--;        // interval shrink to  [left, right-1]
            }
        }
        return nums[left];
    }
};
全部评论

相关推荐

就前几天旅游的时候,打开抖音就经常刷到这类视频:以前是高学历学生、老师、主持人,现在做着团播、擦边主播的工作,以及那些经过精心包装的“职业转型”故事——从铺天盖地的VLOG到所谓的“04年夜场工作日记”,这些内容在初中升学、高考放榜等关键时间节点持续发酵。可以说非常直接且精准地在潜移默化地影响着心智尚未成熟的青少年,使其对特殊行业逐渐脱敏。那我就想问了:某些传播公司、平台运营者甚至某些夜场的老板,你们究竟在传递怎样的价值观?点开那些视频,评论区里也是呈现明显的两极分化:一种是​​经济下行论​​:“现在就业市场已经艰难到这种程度了吗?”​​一种是事实反驳派​​:这些创作者往往拥有名校背景,从事着...
牛客刘北:被环境教育的,为了能拿到足够的钱养活自己,不甘心也得甘心,现在的短视频传播的思想的确很扭曲,但是很明显,互联网玩上一年你就能全款提A6,但你全心全意不吃不喝工作一年未必能提A6,但是在高考中考出现这个的确很扭曲,在向大家传播“不上学,玩互联网也可以轻松年入百万”,不是人变了,是社会在变
预测一下26届秋招形势
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务