【二分查找专题】剑指 Offer 11. 旋转数组的最小数字-跟着帅地玩副业，开拓第二曲线PlayOffer

ShadowyHalo 永久会员 2025年7月29日下午3:28

打卡
class Solution {
public int inventoryManagement(int[] stock) {
int low = 0;
int high = stock.length – 1;
while(low < high){
int mid = low + (high – low) / 2;
if(stock[mid] < stock[high]){
high = mid;
}else if(stock[mid] > stock[high]){
low = mid + 1;
}else{
high -= 1;
}
}
return stock[low];
}
}

0 赞同 0 条回复

youngsir 普通 2024年12月21日下午8:09

打卡

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int l = 0,r = stock.size()-1;
        while(l<r){
            int mid = ((r-l)/2)+l;
            if(stock[mid] < stock[r]){
                r = mid;
            }else if(stock[mid] > stock[r]){
                l = mid + 1;
            }else{
                r--;
            }
        }
        return stock[r];

    }
};

0 赞同 0 条回复

陆狗陆狗普通 2024年12月10日下午11:07

解题思路
– 按照目标节点把数据分成{左侧，目标数据，右侧}，左侧的任一数据都比右侧的全部数据大于等于
– 目标数据是右侧数据中的最小值
– 通过比较stock[mid]和stock[right]的大小去判断mid在哪一侧，但是当stock[mid]=stock[right]是无法判断在哪一侧的，只能让right–去逐渐逼近
【题解1】

class Solution {
    public int inventoryManagement(int[] stock) {
        // 极端情况，完全升序的
        // 【错误点】不能去等于，因为[4,5,8,3,4]会出错
        if (stock[stock.length - 1] > stock[0]) {
            return stock[0];
        }
        int left = 0;
        int right = stock.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 关键看中间点落在哪一部分
            if (stock[mid] > stock[right]) {
                // 大于，说明落在左边,缩小左边（mid本身是不可能的）
                left=mid+1;
            } else if (stock[mid] < stock[right]) {
                // 小于，说明落在右边(mid本身是可能的)
                right=mid;
            } else {
                // 【错误点】
                // 等于
                // 如果是左边重复{3,3,1,3}，需要left=mid
                // 如果是右边重复{3,4,1,3,3,3,3}，也需要left=mid就错误了，需要right=mid
                //  如果是 [10,1,10,10,10]， left=left+1逐步试探就是错误的
                // 最终只能right=right-1这种方式去逐步试探了，即使最右边的点被抛弃了，因为左边有相同的点，所以也没关系
                right=right-1;

            }
        }
        return stock[left];
    }
}

错误点：stock[mid] stock[right]时，mid可能落在左侧{3,3,1,3}，mid也可能落在右侧{3,4,1,3,3,3,3}，如果是 [10,1,10,10,10]， left=left+1逐步试探就是错误的，最终只能right=right-1这种方式去逐步试探了，即使最右边的点被抛弃了，因为左边有相同的点，所以也没关系

0 赞同 0 条回复

黑键〰普通 2024年12月10日下午4:17

/**
 * @param {number[]} stock
 * @return {number}
 */
var inventoryManagement = function(stock) {
    let left = 0
    let right = stock.length - 1
    while(left <= right) {
        let mid = left + Math.floor((right - left)/2)
        if(stock[mid] > stock[right]) {
            left = mid + 1
        } else if(stock[mid] < stock[right]){
            right = mid
        } else {
            right = right - 1
        }
    }
    return stock[left]
};

思路：用中间点的值和左右区间端点的值比较，正常有序升序应该是左小右大，如果中间点的值大于右端点则说明旋转点在右半区间内

0 赞同 0 条回复

Aatorx 永久会员 2024年12月9日下午4:41

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        int l = 0;
        int r = stock.size() - 1;
        while (l < r) {
            int mid = (r - l) / 2 + l;
            if (stock[mid] > stock[r]) {
                l = mid + 1;
            }
            else if (stock[mid] < stock[r]){
                r = mid;
            }
            else {
                r--;
            }
        }
        return stock[l];
    }
};

当stock[mid] = stock[r]时，无法判断mid点在左侧还是右侧，此时执行r–，若r是旋转点，且r与数组中间点的值相同，说明数组全相等，答案也正确。
时间复杂度O(logN)，若数组值全相等则退化为O(N)，空间复杂度O(1)。

0 赞同 0 条回复

Jerry 普通 2024年12月8日下午10:06

class Solution {
public:
    int inventoryManagement(vector& stock) {
        int left = 0, right = stock.size()-1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(stock[mid] < stock[right]){
                right = mid;
            }
            else if(stock[mid] > stock[right]){
                left = mid + 1;
            }
            else if(stock[mid] == stock[right]){
                right--;
            }
        }
        int minval = stock[left];
        if(left+1 < stock.size()) minval = min(minval, stock[left + 1]);
        if(left-1 >= 0) minval = min(minval, stock[left - 1]);
        return minval;
    }
};

时间o(logn)空间o(1)
需注意的点：
1、当stock[mid] == stock[right]时，刚开始写的是right = mid - 1;是错误的，因为有两种可能：
（1）【考虑到了】最小值可能在前半部分，后部分重复；
（2）【没有考虑到】也可能能前半部分都是重复值，而最小值在后半部分。e.g.这种情况：3,3,1,3;。正确操作是right--;。
2、当stock[mid] < stock[right]时，刚开始写的是right = mid - 1;是错误的，因为stock[mid]本身可能就是最小值，这样会跳过。e.g.这种情况：10,10,1,10,10;正确操作是right = mid。
3、最后两行，是为了以防万一没找到最小值加的。不加也可以

        if(left+1 < stock.size()) minval = min(minval, stock[left + 1]);
        if(left-1 >= 0) minval = min(minval, stock[left - 1]);

0 赞同 0 条回复

jaron 普通 2024年12月7日上午10:56

class Solution {
    public int inventoryManagement(int[] stock) {
        int l = 0;
        int r = stock.length - 1;
        // 左闭右开
        while (l < r) {
            // 数组有序
            if (stock[l] < stock[r]) {
                return stock[l];
            }
            int mid = (r + l) / 2;
            if (stock[mid] > stock[l]) {
                l = mid + 1;
            } else if (stock[mid] < stock[l]) {
                r = mid;
            } else {
                // [10, 10, 10, 1, 10, 10]
                // stock[mid]是右边的10，stock[l]是左边的10
                l++;
            }
        }
        return stock[l];
    }
}

0 赞同 0 条回复

Xiang. 永久会员 2024年12月7日上午10:53

思路：该题相较于leetcode153题，多了个可能存在重复的情况，故需要考虑当二分元素 nums[mid] 与区间右端点元素相同时，无法确定最小值所在区间，此时需要去掉右端点的元素即right--，重新进行判断。
使用左开右开区间：
class Solution {
    public int inventoryManagement(int[] stock) {
        int left=-1;
        int right=stock.length-1;
        int mid,num;
        while(left+1!=right){
            num=stock[right];
            mid=((right-left)/2)+left;
            if(stock[mid]<num) right=mid;
            else if(stock[mid]>num) left=mid;
            else right--;
        }
        return stock[right];
    }
}
时间复杂度：o（logn）
空间复杂度：o（1）

0 赞同 0 条回复

lQl 永久会员 2024年12月7日上午12:43

时间复杂度O(logn)
空间复杂度O(1)

class Solution {
    public int inventoryManagement(int[] stock) {
        int l = 0;
        int r = stock.length - 1;
        int result = stock[0];
        while (l <= r) {
            int mid = l + (r - l) / 2;
            System.out.println(r);
            if (stock[mid] > stock[r]) {
                result = stock[mid + 1];
                l = mid + 1;
            } else if (stock[mid] < stock[r]) {
                r = mid;
            } else {
                r--;
            }

        }
        return result;
    }
}

0 赞同 0 条回复

Kisara 普通 2024年12月6日下午11:19


投机取巧是sort函数，也能过但是慢一些

class Solution {
    public int inventoryManagement(int[] stock) {
        Arrays.sort(stock);
        return stock[0];
    }
}

二分还没写，明天补充-_-

一直不理解r--为什么不会丢失最小值，
现在明白了，stock[l] == stock[r]的时候
无法判断值在哪个区间，直接r--可以缩
小范围，因为stock【l】也是这个值，所
以是不会丢失他的，最后答案就为区间收
敛到只有一个元素时
Ologn  o1
class Solution {
    public int inventoryManagement(int[] stock) {
      int l=0;
      int r=stock.length-1;
      if(l>r) return 0;
      int last=stock[r];

      while(lstock[r]){
            l=mid+1;
        }else if(stock[mid] < stock[r])r=mid;
        else r--;
      }
    return stock[l];
    }
}

0 赞同 0 条回复

苯庸普通 2024年12月6日下午8:28

class Solution {
public int findMin(int[] nums) {
int l = 0, r = nums.length-1;
while(l < r){
int m = (l + r)/2;
// 右有序,旋转点在左边
if(nums[m] < nums[r]){
r = m;
}else if(nums[m] > nums[r]){
l = m + 1;
}else{
r–;
}
}
return nums[l];
}
}
思路：相较于之前的二分只判断两种情况，这种需要在等于时缩小右区间
时间：O（lgn）
空间：O（1）

0 赞同 0 条回复

月下足迹普通 2024年12月6日下午8:01

//把stork[mid]的值和stork[right]的值做比较，结果有三种情况
class Solution {
public int inventoryManagement(int[] stock) {
int left = 0;
int right = stock.length – 1;

    while(left < right) {
        int mid = (left + right) / 2;
        if (stock[mid] > stock[right]) {
            left = mid + 1;
        }else if (stock[mid] < stock[right]){
            right = mid;
        }else {
            right --;
        }
    }
    return stock[left];
}

}

0 赞同 0 条回复

迢迢星野普通 2024年12月6日下午7:46

class Solution {
    public int inventoryManagement(int[] stock) {
        int left = 0, right = stock.length - 1;
        while (left < right) {
            // 先去掉两个指针对应的重复元素
            while (left < right && stock[left] == stock[left + 1]) left++;
            while (left < right && stock[right] == stock[right - 1]) right--;

            int mid = left + (right - left) / 2;
            if (stock[mid] > stock[right]) {
                // [mid + 1, r]，这个时候为什么要对 mid + 1 呢？因为 nums[mid] > nums[r]，说明 mid 对应元素不是所求值，跳过即可
                left = mid + 1;
            }else if (stock[mid] < stock[right]){
                // 所求值在 [l, mid] 之间，为什么不对 mid - 1 呢？因为 mid 也有可能是所求值
                right = mid;
            }
            // 没有 nums[mid] == nums[r]，因为 mid 不可能等于 r，并且 r 的左侧没有与它相等的元素（上面已经去重过）
            // 如果没有去重的话，当 nums[mid] == nums[r]，需要缩小右侧范围，r = r - 1;
        }

        return stock[left];
    }
}

思路：二分查找。
时间复杂度：O(logn)
空间复杂度：O(1)

0 赞同 0 条回复

晓宇普通 2024年12月6日下午7:43

class Solution {
public:
    int inventoryManagement(vector<int>& stock) {
        if(stock.size() == 1) return stock.front();
        int l = 0, r = stock.size() - 1, mid;
        while(l < r){
            if(stock[l] < stock[r]) return stock[l];
            int mid = (r - l ) / 2 + l;
            if(stock[mid] < stock[r]) {         // 如果r处id大于mid处的id，那么mid右边是顺序
                r = mid ;
            }else if(stock[mid] > stock[r]){   // 否则右边一定调配过顺序
                l = mid + 1;
            }else{
                r = r - 1;
            }
        }
        return stock[l]; 
    }
    // 时间复杂度:o(lg n); 空间复杂度:o(1)
};

0 赞同 0 条回复

【二分查找专题】剑指 Offer 11. 旋转数组的最小数字

共以下 14 个回答

# 回答此问题取消回复

【二分查找专题】剑指 Offer 11. 旋转数组的最小数字

共以下 14 个回答

# 回答此问题 取消回复

# 回答此问题取消回复