九号球普通 2023年11月20日下午8:01

“`java
class Solution {
public int stockManagement(int[] stock) {
int l = 0;
int r = stock.length – 1;
//最右边的值肯定小于等于最左边的值，否则直接返回最左
if (stock[l] < stock[r]) { return stock[l]; } while (l < r) { int mid = l + (r - l)/2; if (stock[mid] > stock[r]) {
//说明mid在左半区间
l = mid + 1;
} else if (stock[mid] < stock[r]) { //说明mid位于右半区间 r = mid; } else { //mid和r相等，说明有重复元素，无法确定mid位于哪个区间，所以需要遍历 r--; } } return stock[r];

}

0 赞同 0 条回复

招舟子普通 2023年8月31日上午11:17

class Solution {
public int minArray(int[] numbers) {
int l = 0,r=numbers.length-1;

    while(l<r){
        if(numbers[l]<numbers[r]){
        return numbers[l];
    }
        int m = (l+r)/2;
        if(numbers[m]>numbers[l]){
            l=m+1;
        }else if(numbers[m]<numbers[l]){
            r=m;
        }else{
            l++;
        }
    }
    return numbers[l];

}

}
呜呜

0 赞同 0 条回复

jhfuture 普通 2023年8月20日下午8:52

“`java
按照一个图解的思路来的，结果和帅地的思路一样
class Solution {
public int minArray(int[] numbers){
int l=0;
int r=numbers.length-1;
while (lnumbers[l]){
l=m+1;
}else if(numbers[m]}

}

0 赞同 0 条回复

彦，，# 普通 2023年7月21日下午11:55

二分法
int minArray(vector<int>& numbers) {
        if(numbers.size() == 0) return -1;

        int l = 0;
        int r = numbers.size()-1;
        while(l < r)
        {
            int mid = l + (r - l)/2;
            if(numbers[mid] < numbers[r])
            {
                r = mid;
            }else if(numbers[mid] > numbers[r])
            {
                l = mid + 1;
            }else if(numbers[mid] == numbers[r])
            {
                r--;
            }
        }
        return numbers[l];
    }

0 赞同 0 条回复

怀瑾永久会员 2023年7月18日上午1:49

“`C++
int findMin(vector& nums) {
int left = 0;
int right = nums.size() – 1;

// 二分查找，找到旋转数组的最小值
while (left < right) {
    int mid = left + (right - left) / 2;

    if (nums[mid] < nums[right]) {
        // 中间元素小于右侧元素，说明最小值在左半边或者就是中间元素本身
        right = mid;
    } else if (nums[mid] > nums[right]) {
        // 中间元素大于右侧元素，说明最小值在右半边，排除左半边
        left = mid + 1;
    } else {
        // 中间元素等于右侧元素，无法判断最小值在哪一侧，缩小右边界
        right--;
    }
}

// 循环结束时，左右指针重合，找到了最小值
return nums[left];

}

“`

0 赞同 0 条回复

Sexypig. 普通 2023年7月14日下午9:01

不会，建议专门弄一次二分查找的模板，讲讲细节，什么时候while（left<right)什么时候等于，相等时该干什么，不相等时是移动到mid还是移动到mid+1or-1

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int low = 0;
        int high = numbers.size() - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
};

int main() {
    vector<int> numbers = {3, 1, 3};
    cout << Solution().minArray(numbers) << endl;
}

0 赞同 0 条回复

花老爷普通 2023年7月14日下午4:58

遍历找出最小值

class Solution {
    public int minArray(int[] numbers) {
        // sol1
        Arrays.sort(numbers);
        return numbers[0];
        // sol2
        return Arrays.stream(numbers).min().getAsInt();
        // sol3，根据题目特性，第一个遇到的小于numbers数组第一个元素的值一定是最小值
        for (int num : numbers) {
            if (num < numbers[0])
                return num;
        }
        return numbers[0];
    }
}

官解二分查找
时间：平均，O(logn)；最坏，O(logn)
空间：O(1)

class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}

0 赞同 0 条回复

BOZ 普通 2023年7月12日下午5:59

【思路】大致思路是利用二分查找：如果mid<right，在左半数组继续寻找；mid>right，在右半数组继续寻找；两者相等则需要特殊处理。有非常多corner case需要考虑，比如3313/1131。
【复杂度】时间复杂度O(logn)最坏O(n)，空间复杂度O(1)

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

        return r? numbers[r]: numbers[0];
    }
};

0 赞同 0 条回复

江畅普通 2023年7月12日下午4:18

// 旋转数组的最小数字
// 时间复杂度 O(logN)
// 空间复杂度 O(1)
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size() - 1;

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月12日上午10:10

java
class Solution {
    public int minArray(int[] numbers) {
        if(numbers.length <= 0) {
            return -1;
        }

        int left = 0;
        int right = numbers.length - 1;

        while(left < right) {

            if(numbers[left] < numbers[right]) {
                return numbers[left]; //[0,1,2,3]等情况，或者调整到一半有序的时候可以直接退出
            }
            int mid = (right - left)/2 + left;
            if(numbers[mid] > numbers[left]) {
                left = mid + 1;
            } else if(numbers[mid] < numbers[left]) {
                right = mid;
            } else { //numbers[mid] = numbers[left]
                left ++; //右移一位
            }
        }

        return numbers[left];
    }
}

最坏情况下数组元素全相等时时间复杂度为O(N), 一般为O(logN)

0 赞同 0 条回复

屠龙手段普通 2023年7月10日下午5:41

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

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        left = 0
        right = len(numbers) - 1
        while left < right:
            mid = (right - left) // 2 + left
            if numbers[mid] > numbers[right]:
                left = mid + 1
            elif numbers[mid] < numbers[right]:
                right = mid
            else:
                right = right - 1
        return numbers[left]

0 赞同 0 条回复

yxy 普通 2023年7月7日下午1:37

O（logn）时间复杂度

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

0 赞同 0 条回复

Yodl. 普通 2023年7月7日下午1:33

//时间复杂度：O(logn) 空间复杂度：O(1)
class Solution {
public:
    int minArray(vector& numbers) {
        int i = 0, j = numbers.size() - 1;
        while (i < j) {
            int m = (i + j) / 2;
            if (numbers[m] > numbers[j]) i = m + 1;
            else if (numbers[m] < numbers[j]) j = m;
            else j--;
        }
        return numbers[i];
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月6日上午10:30

边界很难处理……

public int minArray(int[] numbers) {
        int l = 0, r = numbers.length-1;
        while(l < r){
            int mid = l + (r - l)/2;
            if(numbers[mid] > numbers[r]){
                l = mid +1;
            }
            else if(numbers[mid] < numbers[r]) r = mid;
            else r--;
        }
        return numbers[l];
    }

0 赞同 0 条回复

局外人普通 2023年7月6日上午9:44

思路：根据旋转数组的特性，最小值将数组分为两部分，以此分类讨论：比较numbers[mid]与numbers[high]的情况
时间复杂度：O(logn) 空间复杂度：O(1)

class Solution {
    public int minArray(int[] numbers) {
        int low=0, high=numbers.length-1;

        while(low<high){
            int mid=low+(high-low)/2;

            if(numbers[mid]<numbers[high]){
                high = mid;
            }else if(numbers[mid]>numbers[high]){
                low = mid + 1;
            }else if(numbers[mid]==numbers[high]){
                high--;
            }
        }

        return numbers[low];
    }
}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年7月6日上午7:49

class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers) - 1

        while l < r:
            if numbers[l] < numbers[r]:
                return numbers[l]

            mid = (r - l) // 2 + l
            if numbers[mid] > numbers[l]:
                l = mid + 1
            elif numbers[mid] < numbers[l]:
                r = mid
            else:
                l += 1

        return numbers[l]

edge case放在loop里：【10，1， 10，10，10】

0 赞同 0 条回复

行动派小彩笔普通 2023年7月5日下午11:04

//空间复杂度O(1), 空间复杂度O(log n)
class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size()-1;
        if(numbers.size()==0)return -1; 
        while(left<right)
        {
            if(numbers[left]<numbers[right])
            {
                return numbers[left];
            }
            int mid = (right-left)/2+left;
            if(numbers[mid]>numbers[left])
            {
                left = mid+1;
            }
            else if(numbers[mid]<numbers[left])
            {
                right = mid;
            }
            else
            {
                left++;
            }
        }
        return numbers[left];
    }
};

0 赞同 0 条回复

Jerry 普通 2023年7月5日下午10:57

 // 二分
class Solution {
    public int minArray(int[] numbers) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int mid = (low + high) >> 1;
            if (numbers[mid] > numbers[high]) {
                low = mid + 1;
            } else if (numbers[mid] < numbers[high]) {
                high = mid;
            } else {
                high--;
            }
        }
        return numbers[low];
    }
}

时间复杂度：O((log2N)
空间复杂度：O(1)

0 赞同 0 条回复

张君雅小妹妹普通 2023年7月5日下午9:28

时间复杂度：O(logN) 极端情况O(N)
空间复杂度：O(1)

class Solution {
    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 = l + ((r - l) >> 1);
            if(numbers[mid] > numbers[l]){
                l = mid + 1;
            } else if(numbers[mid] < numbers[l]){
                r = mid;
            } else {
                l++;
            }
        }
        return numbers[l];


    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月5日下午9:08

//思路：二分缩小范围
public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length - 1;
        while(left < right){
            int mid  = left + (right - left) / 2;
            if(numbers[mid] > numbers[right]){
                left = mid + 1;
            }else if(numbers[mid] < numbers[right]){
                right = mid;
            }else{
                //相等
                int min = numbers[left];
                for(int i = left + 1;i <= right;i++){
                    if(numbers[i] < min){
                        min = numbers[i];
                    }
                }
                return min;
            }
        }
        return numbers[left];
    }

0 赞同 0 条回复

Ming 普通 2023年7月5日下午8:59

不断缩减区域寻找最小数字，假设寻找的数字下标为l，arr[l] arr[mid] 使l++ 砍掉左边

class Solution {
    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[l] < numbers[mid]) {
                l = mid + 1;
            } else if(numbers[l] > numbers[mid]) {
                r = mid;
            } else {
                l++;
            }
        }
        return numbers[l];
    }
}

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

0 赞同 0 条回复

张开怀普通 2023年7月5日下午8:21

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

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

0 赞同 0 条回复

伏月三十普通 2023年7月5日下午7:47

class Solution {
    public int minArray(int[] numbers) {
        int left=0;
        int right=numbers.length-1;
        while(left<right){
            //判断一下极端情况
            if(numbers[left]<numbers[right]){
                return numbers[left];
            }
            int mid=(right-left)/2+left;
            if(numbers[mid]>numbers[left]){
                //此时旋转点不可能落在左边，把左边区域缩小
                left=mid+1;
            }else if(numbers[mid]<numbers[left]){
                //旋转点落在了左边，把右边区域缩小 mid所在的位置可能是旋转点
                right=mid;
            }else if(numbers[mid]==numbers[left]){
                //存在了重复
                left=left+1;
            }

        }
        return numbers[left];
    }
}

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

0 赞同 0 条回复

Dsjh 普通 2023年7月5日下午5:56

MY

class Solution {
public:
    int findMin(vector<int>& nums) {
        int l=-1,r=nums.size();
        while(l+1!=r){
            int mid = l+(r-l)/2;
            // 左区域大于 back，也可能等于
            if(nums[mid]>nums.back()) l=mid;
            // 右区域小于 back，也可能等于
            else if(nums[mid] < nums.back()) r=mid;
            // 相等时，怎么区分左右区域
            // 如果从 mid 到 nums.size()-1 都相等，则 mid 属于右区域
            // 如果不相等，属于左区域
            else{
                int i=mid;
                while(i<nums.size()){
                    if(nums[i] == nums[mid])
                        i++;
                    else
                        break;
                }
                if(i==nums.size()){
                    r=mid;

                }
                else{
                    l=mid;
                }
            }
        }
        return nums[r];
    }
};

0 赞同 0 条回复

désire. 普通 2023年7月5日下午4:42

Cpp实现：
class Solution {
public:
int minArray(vector& numbers) {
int left = 0;
int right = numbers.size() – 1;
while(left < right)
{
int mid = (left + right) / 2;
if(numbers[mid] > numbers[right])
{
left = mid + 1;
}
else if(numbers[mid] < numbers[right])
right = mid;
else
right–;
}
return numbers[right];
}
};

0 赞同 0 条回复

名字什么的好麻烦普通 2023年7月5日下午4:09

二分查找

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

0 赞同 0 条回复

小吕普通 2023年7月5日下午2:58

c++实现，
int minArray(vector& numbers) {
int left = 0;
int right=numbers.size()-1;

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

0 赞同 0 条回复

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

共以下 27 个回答

MY

# 回答此问题取消回复

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

共以下 27 个回答

MY

# 回答此问题 取消回复

# 回答此问题取消回复