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

ppopp 普通 2023年8月30日下午10:51

class Solution {
public:
int minArray(vector& numbers) {
int len = numbers.size();
int left = 0;
int right = len – 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 right--;
    }
    return numbers[left];
}

};//滴滴

0 赞同 0 条回复

hi 普通 2023年8月16日上午10:40

注意数组中具有重复元素，需要去掉数组后面与前面的重复元素
去掉后边重复元素的旋转数组具有特点：有序或者具有二分特性

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int n = numbers.size() - 1;
        while(n > 0 && numbers[0] == numbers[n]) n--;
        if(numbers[n] >= numbers[0]) return numbers[0];

        int l = 0, r = n;
        while(l < r){
            int mid = (l + r) >> 1;
            if(numbers[mid] >= numbers[0]) l = mid + 1;
            else r = mid;
        }
        return numbers[r];
    }
};

0 赞同 0 条回复

艺普通 2023年8月3日下午9:40

“`c++代码
class Solution {
public:
int minArray(vector& numbers) {
return *min_element(numbers.begin(), numbers.end());
}
};

0 赞同 0 条回复

波雅汉库克普通 2023年8月1日下午3:52

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

时间 O（logn）
空间 o(1)

0 赞同 0 条回复

普通 2023年7月31日下午11:07

c++ 没用二分查找
class Solution {
vector invec;
int tmax=9999;
public:
int minArray(vector& numbers)
{
for(int t=0;t<2;t++)
{
for(int i=0;i<numbers.size();i++)
{
invec.push_back(numbers[i]);
if(tmax>numbers[i])
tmax=numbers[i];

        }

      }   
      int s=1;
      for(int i=0;i<invec.size()-1;i++)
      {   
          if(s==numbers.size())
          break;
                 if(invec[i+1]>=invec[i])
                    s++;
                    else
                    s=1;
      }
      if(s<numbers.size())
        return 0;
          return tmax;

 }

};

0 赞同 0 条回复

CaCO3 永久会员 2023年7月31日下午3:16

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

        }
    }
    return numbers[l];
}

}

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

0 赞同 0 条回复

Mby 普通 2023年7月29日下午8:37

class Solution {
    public int minArray(int[] numbers) {
        //时间复杂度O（n）
        int l = 0;
        int r = numbers.length - 1;
        while(l < r){
            if(numbers[l] < numbers[r]){
                return numbers[l];
            }

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

0 赞同 0 条回复

枫梓。普通 2023年7月27日下午4:12

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lt = 0, rt = nums.size() - 1;
        if(nums[lt] < nums[rt] || lt == rt) return nums[lt];
        while(lt < rt) {
            int mid = (rt - lt) / 2 + lt;
            if(nums[mid] < nums[rt]) {
                rt = mid;
            } else if (nums[mid] > nums[rt]) {
                lt = mid + 1;
            } else {
                rt--;
            }
        }
        return nums[lt];
    }
};

空间O(1)
时间O(logn)

0 赞同 0 条回复

今天你刷题了嘛普通 2023年7月26日下午11:36

class Solution {
    public int minArray(int[] numbers) {
        int left = 0;
        int right = numbers.length-1;
        int mid;
        while(left<=right){
            // 旋转回来的特殊情况
            if(numbers[left]<numbers[right]){
                return numbers[left];
            }
            mid = (right-left)/2 + left;
            if(numbers[mid]>numbers[right]) {
                left = mid+1;
            } else if(numbers[mid]<numbers[right]){
                right = mid;
            } else{
                // 当旋转点 pivot == numbers[right]时，可以砍掉right这个重复的点
                right--;
            }
        }
        return numbers[left];
    }
}

时间复杂度：O（logn）
空间复杂度：O（1）

0 赞同 0 条回复

北辰普通 2023年7月26日下午9:46

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

时间复杂度：最好情况：o(log(n)) 最差情况：o((n))
空间复杂度：o(1)

0 赞同 0 条回复

CKX 普通 2023年7月26日下午3:48

func minArray(numbers []int) int {
    left, right := 0, len(numbers) - 1
    for left <= right {
        mid := left + (right - left)/2
        if numbers[mid] > numbers[right] {
            left = mid + 1
        } else if numbers[mid] < numbers[right] {
            right = mid
        } else if numbers[mid] == numbers[right] {
            right--
        }
    }
    return numbers[left]
}

时间O(logn)
空间O(1)

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月25日下午9:15

代码

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

0 赞同 0 条回复

NullPointerException 普通 2023年7月25日下午12:51

class Solution {
public int minArray(int[] numbers) {
//从左到右只能递增中间会有断点
//二分找最小值如果 right>=mid 那么右边递增最小在左
//如果 right<=mid 那么最小在 mid 后面
int left =0;
int right = numbers.length -1 ;
int mid;
while(left<right)
{
mid=(left+right)/2;
if(numbers[mid]>numbers[right])//中间大于右边一定在中间到右边
{
left = mid +1;
}else if(numbers[mid]<numbers[right]) //右边是递增
{
right =mid;
}else//2种有可能是没变化那么在左边有可能是在中间无法判断让right–
{
right–;
}

        }
        return numbers[left];
}

}

0 赞同 0 条回复

Marshan 普通 2023年7月24日下午9:27

第二次碰到还是没做出来

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

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

        }
        return numbers[l];
    }
};

0 赞同 0 条回复

Luminous 普通 2023年7月24日下午12:47

以下是代码：

class Solution {
    public int minArray(int[] numbers) {
        if(numbers.length==1) return numbers[0];
        int left=0,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{
                right--;
            }
        }
        return numbers[left];
    }
}

0 赞同 0 条回复

人生何处不青山普通 2023年7月24日上午11:24

难点还是想到是和右端点比较还有就是r–的操作

function minArray(numbers: number[]): number {
    let l = 0, r = numbers.length - 1;
    while (l < r) {
        let mid = (l + r) >>> 1;
        if (numbers[mid] > numbers[r]) {
            l = mid + 1;
        } else if (numbers[mid] === numbers[r]) {
            r--;
        } else {
            r = mid;
        }
    }
    return numbers[l];
};

0 赞同 0 条回复

June 普通 2023年7月23日下午10:23

func minArray(numbers []int) int {
    var l int = 0
    var r int = len(numbers) - 1

    for l < r {
        mid := (r-l)/2 + l
        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月23日下午10:19

7.23
Day15：下面是代码


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

0 赞同 0 条回复

#00456B 普通 2023年7月23日下午7:41

class Solution {
public:
    int minArray(vector& numbers) {
        //只有一次旋转，所以就是比较mid和right的值
        int left = 0;
        int right = numbers.size() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            int target = numbers[right];
            if(numbers[mid] > target){
                //最小值在[m+1,r]
                left = mid + 1;
            }
            else if(numbers[mid] < target){
                //最小值在[l,m]
                right = mid;
            }
            else{
                //因为存在重复的情况，所以当mid == right的值时，right--，缩小范围
                //e.g [0,0,1,1,1]
                right--;
            }
        }
        return numbers[left];
    }
};

0 赞同 0 条回复

AD钙奶普通 2023年7月23日下午3:57

其实主要找的就是两段有序序列的边界，第二段序列的左边界就是我们要的答案。
采用左闭右闭的原则，r不能跳到mid – 1，而要跳到mid，原因是因为mid本身的元素可能就是最小值。

class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while(l <= r) {
            int mid = l + r >> 1;
            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月23日下午3:48

//二分法
class Solution {
    
    public int minArray(int[] numbers) {
        if(numbers.length == 1) return numbers[0];

        int l = 0;
        int r = numbers.length - 1;

        while(l <= r){
            int mid = l + ((r - l) >> 1);

            if(numbers[mid]  > numbers[r]){
                //最小值在[m+1,r]
                l = mid + 1;
            }else if(numbers[mid] < numbers[r]){
                //最小值在[i,m]
                r = mid;
            }else{
    //r=r-1就是将区间减少了1个，删除的最后这个元素（下标j），在删除后的区间仍存在。
    //简单的说，因为相等，所以删掉一个留下一个，我们在剩下区间搜索，仍可以搜索到删除的那个元素值。
                r = r - 1;
            }
        }

        return numbers[l];
    }
}

0 赞同 0 条回复

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

共以下 21 个回答

# 回答此问题取消回复

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

共以下 21 个回答

# 回答此问题 取消回复

# 回答此问题取消回复