[binary_search]旋转数组的最小数字

旋转数组的最小数字

http://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba

题目:

把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。
NOTE:给出的所有元素都大于0,若数组大小为0,请返回0。

思路:

这道题花费了好多时间,15:19--0:58,看起来如此简单的一道题花费的时间让我崩溃。遇到二分边界就是噩梦。
一开始思路不清晰摸索了一番发现即使这种旋转数组二分依然可以查找就是要分情况。后来发现不是二分,而是用二分直接找断点。查找的目标是mid的哪一边的两端不是严格正序就是一个中断,然后思路混乱花了好久才分出所有情况:
图片说明
1.这里设计到分割的覆盖情况(说白了就是没分割好情况。。。)中断点在左边的情况和在右边的情况,则相应的另一边肯定是合法的,可能是严格升序也可能是不降序,所以一共有四种组合排除掉两边都是严格降序(不可能的),则一边严格一边不严格的情况,一定是属于间断点出现的情况(跟最开始的讨论重合了。。。),然后就剩下两边都不降的情况,其实就是mid/low/high三点相同。所以逻辑上就就三条通路,左边有间断,右边有间断和两边无法判断。
2.考虑两边无法判断的情况,可以一开始将两边重合的都消除,反正他们不会是结果(全相等除外,这里用下标控制不会全相等),但是首先两边都消除可能让任意一边都有可能越界(断点跑出low/high),(要么是一个不同的值要么越界),左边越界正好在最小值上,右边越界会越过最小值,所以在无法判断的时候就让左边移动。而且也不能在一开始只消除一次,一开始消除后之后的切割也可能切出三点相同的情况。所以得放在每一次更新low/high里面。
图片说明
3.越界之后会发生什么。越界之后(只有左边会)如果不加控制那么会等同于三点相同的情况(跳过两边有断点的情况,哪边都不迭代,这个时候mid大于low小于high,就是那种不可能的情况)(不是二分查找,二分会往界外的断点逼近),然后左边移动,因此最终是high的节点。解决的方法是当他越界之后本身就可以退出了。。。
4.再来说说坑爹的边界。二分的时候要注意更新边界是mid+1,不加1会导致目标不在查找表里时,最终在缺失间隔处的两个节点上死循环。加了1同样会越界但是二分里越界没事,然后中止条件也是=或者low>high。这道题不加1同样会死循环,在断点左右,然后加了1就是上面的越界情况了。

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

class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        int low=0, high=rotateArray.size()-1, mid;
       while(low < high && rotateArray[low]>=rotateArray[high]){
           mid = (low + high)/2;
           if(rotateArray[low] > rotateArray[mid]){
               high = mid;
           }
           else if(rotateArray[mid] > rotateArray[high]){ //如果省区else是if选择形态的,则要更新mid
               low = mid + 1;//+1是为了可以迭代,两个方向的迭代都没有加1会陷入死循环(中断处卡在两个元素中间,同二分查找),而加了1的又会越界
               //在这里,越界组基本是导致两个迭代都失效(这里的左右下表迭代是中断点但并不是朝中断点的方向出发,而是有就出发没有<越界>就什么都不坐),同三点相等,于是左端会移动)
           }
           else {
               ++low;
           }
//1.若是low/high/mid都相同的情况,一开始是选择去除相同的首尾,且循环去除,且在一开始就去除,但问题是去除会使low/high跳动,
// low经过中断处是最小值,high经过中断越过了最小值,(即使通过越界直接判断结果,low越界结果就是low,high越界结果是high后一个不统一),所以只让low跳动就好了,即(]
//2.如果越界按照上面说的就是左端不断移动到low high相遇退出则结果错误(一开始消除三点相等只外面一次,于是越界后是上下标不更新死循环,但问题不在于三点相等,而在于越界!)
       }
       return rotateArray[low];
    }
};

int main() {
    Solution s;
    s.minNumberInRotateArray(vector<int>{4, 5, 6, 1, 2, 3});
    return 0;
}

我真是吃了si,一道题写一天

全部评论

相关推荐

避坑恶心到我了大家好,今天我想跟大家聊聊我在成都千子成智能科技有限公司(以下简称千子成)的求职经历,希望能给大家一些参考。千子成的母公司是“同创主悦”,主要经营各种产品,比如菜刀、POS机、电话卡等等。听起来是不是有点像地推销售公司?没错,就是那种类型的公司。我当时刚毕业,急需一份临时工作,所以在BOSS上看到了千子成的招聘信息。他们承诺无责底薪5000元,还包住宿,这吸引了我。面试的时候,HR也说了同样的话,感觉挺靠谱的。于是,我满怀期待地等待结果。结果出来后,我通过了面试,第二天就收到了试岗通知。试岗的内容就是地推销售,公司划定一个区域,然后你就得见人就问,问店铺、问路人,一直问到他们有意向为止。如果他们有兴趣,你就得摇同事帮忙推动,促进成交。说说一天的工作安排吧。工作时间是从早上8:30到晚上18:30。早上7点有人叫你起床,收拾后去公司,然后唱歌跳舞(销售公司都这样),7:55早课(类似宣誓),8:05同事间联系销售话术,8:15分享销售技巧,8:30经理训话。9:20左右从公司下市场,公交、地铁、自行车自费。到了市场大概10点左右,开始地推工作。中午吃饭时间大约是12:00,公司附近的路边盖饭面馆店自费AA,吃饭时间大约40分钟左右。吃完饭后继续地推工作,没有所谓的固定中午午休时间。下午6点下班后返回公司,不能直接下班,需要与同事交流话术,经理讲话洗脑。正常情况下9点下班。整个上班的一天中,早上到公司就是站着的,到晚上下班前都是站着。每天步数2万步以上。公司员工没有自己的工位,百来号人挤在一个20平方米的空间里听经理洗脑。白天就在市场上奔波,公司的投入成本几乎只有租金和工资,没有中央空调。早上2小时,晚上加班2小时,纯蒸桑拿。没有任何福利,节假日也没有3倍工资之类的。偶尔会有冲的酸梅汤和西瓜什么的。公司的晋升路径也很有意思:新人—组长—领队—主管—副经理—经理。要求是业绩和团队人数,类似传销模式,把人留下来。新人不能加微信、不能吐槽公司、不能有负面情绪、不能谈恋爱、不能说累。在公司没有任何坐的地方,不能依墙而坐。早上吃早饭在公司外面的安全通道,未到上班时间还会让你吃快些不能磨蹭。总之就是想榨干你。复试的时候,带你的师傅会给你营造一个钱多事少离家近的工作氛围,吹嘘工资有多高、还能吹自己毕业于好大学。然后让你早点来公司、无偿加班、抓住你可能不会走的心思进一步压榨你。总之,大家在找工作的时候一定要擦亮眼睛,避免踩坑!———来自网友
qq乃乃好喝到咩噗茶:不要做没有专业门槛的工作
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务