V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
xiaoming1992
V2EX  ›  LeetCode

leetcode 33 解法求解释

  •  
  •   xiaoming1992 · 158 天前 · 533 次点击
    这是一个创建于 158 天前的主题,其中的信息可能已经有所发展或是发生改变。

    题目: 33. Search in Rotated Sorted Array 一个很清晰简洁的解法: Clever idea making it simple

    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            
            double num = (nums[mid] < nums[0]) == (target < nums[0])
                       ? nums[mid]
                       : target < nums[0] ? -INFINITY : INFINITY;
                       
            if (num < target)
                lo = mid + 1;
            else if (num > target)
                // 这儿为什么不能 -1 ?
                hi = mid;
            else
                return mid;
        }
        return -1;
    }
    

    这个解法省了我几万个脑细胞, lo = mid + 1 很好理解, 但是 hi = mid - 1 为什么出错, 我想破脑袋都没想明白...

    lostvincent
        1
    lostvincent  
       158 天前   ❤️ 2
    int mid = ( lo + hi ) / 2 这步,其实是 floor( ( lo + hi ) / 2 )
    如果 lo = mid + 1 的话,lo 正好是 target,那么 hi 会递减到 lo + 1 为止,然后 下一步 ( lo + hi ) / 2 就是 lo
    如果 hi = mid - 1 这步执行之后,hi 正好是 target,那他就永远找不到了,因为 lo 递增到 hi - 1 之后,( lo + hi ) / 2 还是 lo

    你可以试试 nums = [1, 2, 3, 4, 5] target = 2
    lostvincent
        2
    lostvincent  
       158 天前   ❤️ 1
    上一楼写错 case 了,当成找不大于不小于到了,抱歉
    lostvincent
        3
    lostvincent  
       158 天前   ❤️ 1
    他这里是 while lo < hi, hi = mid - 1 之后,如果 hi == lo,就不会进 while,这时候如果 nums[lo] == target,那么结果就会变成 -1
    更正 case:nums = [4,5,6,7,0,1,2] target = 0
    xiaoming1992
        4
    xiaoming1992  
    OP
       158 天前 via Android
    @lostvincent 非常感谢!这个题目昨晚卡了我很久,一直想不通 high - 1 和 low + 1 有什么区别,原来区别出在 floor 这儿,感谢感谢!
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3909 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 19ms · UTC 08:27 · PVG 16:27 · LAX 00:27 · JFK 03:27
    ♥ Do have faith in what you're doing.