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

NULL 普通 2024年3月25日下午11:32

class Solution {
/**
* 寻找旋转排序数组中的最小值（数组中可能有重复元素）
*/
public int findMin(int[] nums) {
// 初始化左右边界
int left = 0, right = nums.length – 1;

    // 去除左右边界上的重复元素
    while (left < right && nums[left] == nums[right]) 
        right--; // 移动右边界，直到左右边界上的元素不相等

    // 开始二分查找
    while (left < right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;   
        // 如果中间元素大于右边界元素，则最小值一定在 mid 的右边，更新左边界为 mid + 1
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            // 否则，最小值一定在 mid 的左边（包括 mid），更新右边界为 mid
            right = mid;
        }
    }
    // 最后 left 和 right 指向的位置一定是最小值所在的位置，直接返回该值
    return nums[left];
}

}

0 赞同 0 条回复

机电皮怪永久会员 2024年3月23日下午2:34

“`C++

class Solution {
public:
//mid大于右边界证明min在mid的右边
//mid小于右边界证明min在mid的左边
int stockManagement(vector& stock) {
if(stock.empty() true)
{
return -1;
}
int left = 0;
int right = stock.size() – 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年3月23日上午2:19

有序旋转数组，找出最小开始的值，用二分查找

class Solution {
    public int stockManagement(int[] stock) {
        int l = 0 , r = stock.length - 1;
        while (l < r) {
            int m = (r - l) / 2 + l;
            if (stock[m] > stock[r]) {
                l = m + 1;
            } else if (stock[m] < stock[r]) {
                r = m;
            } else {
                r--;
            }
        }
        return stock[l];
    }
}

0 赞同 0 条回复

kfaebot 普通 2024年3月20日下午3:19

class Solution {
public:
    int stockManagement(vector<int>& stock) {
        int left=0;
        int right=stock.size()-1;

        while(left<right){
            int middle=(left+right)/2;

            if(stock[middle]>stock[right]){
                left=middle+1;
            }
            else if(stock[middle]<stock[right]){
                right=middle;
            }
            else if(stock[middle]==stock[right]){
                right=right-1;
            }
        }
        return stock[left];
    }
};
//时间复杂度O(logN)

0 赞同 0 条回复

方铎码农普通 2024年3月18日下午11:23

// 原库存表按商品 id 升序排列。现因突发情况需要进行商品紧急调拨，管理员将这批商品 id 提前依次整理至库存表最后。
// 即升序列表的旋转
// 原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：
// 若旋转 4 次，则可以得到 [4,5,6,7,0,1,2]
// 若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]
class Solution {
    public int stockManagement(int[] stock) {
        int l = 0, h = stock.length - 1;
        while(l < h){
            int pivot = l + (h - l) / 2;
            if(stock[pivot] < stock[h]){
                // stock[pivot]在最小值右侧
                h = pivot;
            } else if (stock[pivot] > stock[h]){
                // pivot在最小值左侧
                l = pivot + 1;
            } else {
                h -= 1;
            }
       } 
       return stock[l];
    }
}

时间复杂度：O(logn),最坏 O(N)
额外空间复杂度：O(1)

0 赞同 0 条回复

言之命至普通 2024年3月18日下午11:21

思路：二分通过比较中间值的大小来确定旋转点的位置

public int minArray(int[] numbers) {

        int l = 0;
        int r = numbers.length - 1;
        while(l < r) {
            if(numbers[l] < numbers[r]){
                return numbers[l];
            }

            int mid = (r + l) / 2;
            if(numbers[mid] > numbers[l]){///最小值在mid前
                l = mid + 1;
            } else if(numbers[mid] < numbers[l]){ ////最小值在mid后  
                r = mid;
            } else {
                l++;
            }
        }

        return numbers[l];
    }

时间复杂度：O(logn),最坏 O(N)
额外空间复杂度：O(1)

0 赞同 0 条回复

MARS 普通 2024年3月18日下午11:15

还挺难的，没想出来

/**
 * @param {number[]} stock
 * @return {number}
 */
var stockManagement = function (stock) {
    if (stock.length == 1) return stock[0]
    let left = 0, right = stock.length - 1
    while (left < right) {   //[left  mid right]    ---right 中有个最小值
        if (stock[left] < stock[right]) return stock[left]
        let mid = Math.floor((left + right) / 2)
        if (stock[mid] > stock[left]) {   //最小值在mid前
            left = mid+1
        } else if (stock[mid] < stock[left]) {  //最小值在mid后  
            right = mid 
        } else {  //==
           left++
        }
    }
    return stock[left]
};

0 赞同 0 条回复

mpweixin用户普通 2024年3月18日下午9:49

java
class Solution {
public int findMin(int[] nums) {
int low = 0;
int high = nums.length – 1;
while(low < high){
int pivot = low + (high – low) / 2;
if(nums[pivot] < nums[high]){
high = pivot;
}else{
low = pivot + 1;
}
}
return nums[low];
}
}
提交

0 赞同 0 条回复

mpweixin用户普通 2024年3月18日下午7:40

public int stockManagement(int[] stock) {
int l=0,r=stock.length-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=r-1;
}
}
return stock[l];
}
思路：二分通过比较中间值的大小来确定旋转点的位置

0 赞同 0 条回复

一个达不刘普通 2024年3月18日下午5:30

class Solution {
public:
int stockManagement(vector& stock) {
int low =0, high = stock.size()-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 条回复

RunAsOne 普通 2024年3月18日下午4:24

时间复杂度O(logN)

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

0 赞同 0 条回复

Jimmy 普通 2024年3月18日下午2:26

实践复杂度O(logN)，空间复杂度O(1)

class Solution {
public:
    int stockManagement(vector<int>& stock) {
        int low = 0;
        int high = stock.size()-1;
        while(low < high){
            int mid = low + (high-low)/2;
            if(stock[mid]<stock[high])//旋转点位于左排序数组
            {
                high = mid;//假设旋转点在闭区间内，因为旋转点处的值是最小值而stock[mid]<stock[high]，
                //stock[mid]可能是最小值，所以high = mid;
            }else if(stock[mid]>stock[high])//旋转点位于右排序数组
            {
                low = mid + 1;//stock[mid]>stock[high]，stock[mid]不可能是旋转点，所以low = mid+1
            }else{
                high--;
            }
        }
        return stock[low];
    }
};

0 赞同 0 条回复

紫芝普通 2024年3月18日下午2:19

思路：int begin = 0, end = stock.size()-1, mid;
s[begin] < s[end]: return s[begin]
s[begin] > s[end]:
mid > begin: begin = mid + 1;
mid < begin: end = mid;
mid begin: begin = mid + 1;
s[begin] s[end]:
mid > begin: begin = mid + 1;
mid < begin: end = mid;
mid begin: begin = begin + 1; (这种情况不能确定最小值在mid的左边还是右边)

“`c++
class Solution {
public:
int stockManagement(vector& stock) {
int begin = 0, end = stock.size()-1, mid;
while (begin < end-1) { if (stock[begin] < stock[end]) return stock[begin]; else { mid = begin + (end - begin)/2; if (stock[mid] > stock[begin]) begin = mid + 1;
else if (stock[mid] < stock[begin]) end = mid; else { if (stock[begin] > stock[end]) begin = mid + 1;
else begin++;
}
}
}
return min(stock[begin], stock[end]);
}
};
“`

0 赞同 0 条回复

Yuki 永久会员 2024年3月18日下午2:14

挺抽象的
https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/solutions/2694041/xun-zhao-xuan-zhuan-pai-xu-shu-zu-zhong-kaf1n

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月18日上午7:59

class Solution {
public:
    int stockManagement(vector<int>& stock) {
        int l = 0, r = stock.size() - 1;
        while(l < r) {
            int mid = l + (r - l) / 2;
            if(stock[mid] > stock[r]) l = mid + 1; // 为什么要跟右边界比较
            else if(stock[mid] < stock[r]) r = mid;  // 因为右边的值较小，当>右边界时，要把左边界往右移动，减小当前值
            else r--;// 如果当前值<右边界时，当前值是还有可能成为那个最小值的，因此不能-1
        }
        return stock[l];
    }
};

0 赞同 0 条回复

Raphtalia. 普通 2024年3月17日下午11:50

class Solution {
public:
int stockManagement(vector& stock) {
int n = stock.size();
int l = 0, r = n – 1;
while(l < r){
int mid = (l + r) / 2;
if (stock[r] < stock[mid]){
l = mid + 1;
}else if(stock[r] > stock[mid]){
r = mid;
}else{
r -= 1;
}
}
return stock[r];
}
};
时间复杂度O（logn）

0 赞同 0 条回复

云无深雁影普通 2024年3月17日下午10:50

class Solution {
public int stockManagement(int[] stock) {
int begin = 0;
int end = stock.length – 1;
while(begin < end){
int mid = (begin + end) / 2;
if(stock[mid] < stock[end]){
end = mid;
}
else if(stock[mid] > stock[end]){
begin = mid + 1;
}
else
end–;
}
return stock[begin];
}
}
//二分查找，以上为看答案后方法空间O1 时间Ologn
//以下为原方法，也是二分查找，实现的复杂一些空间Ologn 时间Ologn
class Solution {
public int stockManagement(int[] stock) {
return halfSearch(stock,0,stock.length-1);
}

private int halfSearch(int[] stock,int begin,int end){
    if(begin >= end )
        return stock[begin];
    int head = stock[begin];
    int tail = stock[end];
    int mid = (begin + end) / 2;
    if(mid > 0 && stock[mid] < stock[mid-1])
            return stock[mid];
    if(stock[mid] <= tail && stock[mid] != head){
        return halfSearch(stock,begin,mid-1);
    }
    if(stock[mid] > head && stock[mid] != tail){
        return halfSearch(stock, mid+1, end);
    }
    int valueInAfter = halfSearch(stock,mid+1,end);
    if(valueInAfter < stock[mid])
        return valueInAfter;
    else
        return halfSearch(stock,begin,mid-1);

}

}

0 赞同 0 条回复

heathhou 普通 2024年3月17日下午9:47

class Solution {
public:
    int stockManagement(vector<int>& stock) {
        int l = 0;
        int r = stock.size() - 1;
        // 当l==r的时候，数组中只有一个元素了，就不用判断了
        while(l < r){
            // 旋转到恢复原样
            if(stock[l] < stock[r]){
                return stock[l];
            }

            int mid = (r - l) / 2 + l;
            if(stock[mid] > stock[l]){
                l = mid + 1;
            }else if(stock[mid] == stock[l]){
                l = l + 1;
            }else{
                r = mid;
            }
        }

        return stock[l];
    }
};

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月17日下午9:35

class Solution {
    public int stockManagement(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+l;
            int mid=(r+l)/2;
            if(stock[mid]>stock[l]) l=mid+1;
            else if(stock[mid]<stock[l]) r=mid;
            else l++;
        }
        // if(stock[l+1]<stock[l]) return stock[l+1];
        return stock[l];
    }
}

时间复杂度：O(logn)
额外空间复杂度：O(1)

0 赞同 0 条回复

王位詮釋普通 2024年3月17日下午7:24

暴力法，直接遍历数组
class Solution {
    public int stockManagement(int[] stock) {
        int min = Integer.MAX_VALUE;
        for(int i=0;i<stock.length;i++){
            min = min>stock[i]?stock[i]:min;
        }
        return min;
    }
}
时间复杂度：O(n)
二分法，逐个缩减范围
class Solution {
    public int stockManagement(int[] stock) {
        int l = 0;
        int r = stock.length-1;
        while(l<r){
            int mid = l+(r-l)/2;
            if(stock[l]<stock[r]){//没有进行移动或者移动次数为数组长度整数倍
                return stock[l];
            }else{//移动了数组
                if(stock[mid]>stock[l]){
                    l = mid+1;
                }else if(stock[mid]<stock[r]){
                    r = mid;
                }else{
                    l++;
                }
            }
        }
        return stock[l];
    }
}
思路：数组可能移动次数为数组长度的整数倍，这时候相当于不移动数组，并且由于数组最开始时候是有序的，所以这种情况直接返回第一个元素即可；如果数组移动的次数不是的话，那数组就会分为两段，一段是值较大的部分，一段是值较小的部分，我们通过二分法每次获取mid的值，比较mid处数组值与left和right所在值的大小，从而缩小空间，如果stcok[left]<stock[mid]，则说明最小值是在mid和right之间，如果stock[right]>stock[mid]，说明最小值是在left和mid之间，否则就是mid和left处值相等或者mid和right处值相等，这时候没办法判断是在哪一部分，但是一定不是left所处的值，让left++，继续比较。
时间复杂度：O(lgn)

0 赞同 0 条回复

神经蛙普通 2024年3月17日下午4:53

class Solution {
public:
int stockManagement(vector& stock) {
int left = 0;
int right= stock.size() -1;
while(left < right){
if(stock[left] < stock [right])
{
return stock[left];
}
int mid = (right +left)/2;
if(stock[mid] > stock[left]){
left = mid + 1;
}
else if(stock[mid] < stock[left]){
right = mid;
}
else{
left++;
}
}
return stock[left];
}
};
时间复杂度O（logN）空间复杂度O（1）

0 赞同 0 条回复

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

共以下 21 个回答

# 回答此问题取消回复

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

共以下 21 个回答

# 回答此问题 取消回复

# 回答此问题取消回复