剑指 Offer 11. 旋转数组的最小数字-7月22日

2021-04-11 08:28

阅读：416

标签：solution 直接 -- number mina 条件判断 loading 查找 question

题目

剑指 Offer 11. 旋转数组的最小数字

技术图片

我的思路

显然用二分查找，时间复杂度logn，最坏情况可能达到n。

要注意二分查找的边界条件判断，以及如果无法判断此次二分是取左或者去右时，可以尝试把上边界下标减1，再重新二分（安全地缩小边界）。

我的实现

class Solution {
public:
    int minArray(vectorint>& numbers) {
        int low = 0;
        int high = numbers.size()-1;
        int s;
        while(low!=high){
            s = low + (high - low)/2;
            if(numbers[high]>numbers[low]) return numbers[low];
            else if(numbers[high]=numbers[low]) low = s + 1;
            else if(numbers[high] s;
            else if(numbers[high]==numbers[low]){high--;}
        }
        return numbers[low];
    }
};
//二分查找
/*
先把两个指针low和high 指向数组首尾。若最小元素的指针（下标）是m，二分过程中的分界下标是s。
可能存在以下几种情况：
1.n[high]>n[low] return n[low]
2.n[high]=n[low] low = s+1
3.n[high]*/

拓展学习

为什么官方的二分法的题解很多都是写的low + (high - low) // 2 而不是 (high + low) // 2?

(high + low) 在两者较大时会发生整型越界!

剑指 Offer 11. 旋转数组的最小数字-7月22日

标签：solution 直接 -- number mina 条件判断 loading 查找 question

原文地址：https://www.cnblogs.com/BoysCryToo/p/13360650.html

上一篇：Javascript模块化编程发展历史

下一篇：常用限流算法与Guava RateLimiter源码解析

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：剑指 Offer 11. 旋转数组的最小数字-7月22日
文章链接：http://soscw.com/index.php/essay/74187.html

亲，登录后才可以留言！

剑指 Offer 11. 旋转数组的最小数字-7月22日

题目

剑指 Offer 11. 旋转数组的最小数字

我的思路

我的实现

拓展学习

评论

热门文章

推荐文章

最新文章

置顶文章