likes
comments
collection
share

二分法(TS):第一个错误的版本

作者站长头像
站长
· 阅读数 5

你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。假设你有 n 个版本 [1, 2, ..., n],你想找出导致之后所有版本出错的第一个错误的版本。你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1:

输入:n = 5, bad = 4

输出:4

解释:

调用 isBadVersion(3) -> false

调用 isBadVersion(5) -> true

调用 isBadVersion(4) -> true

所以,4 是第一个错误的版本。

示例 2:

输入:n = 1, bad = 1

输出:1

 

提示:

  • 1 <= bad <= n <= 231 - 1

解法

由题可知版本的序列是有序的,因此可以直接采用二分法,如下:

/**
 * The knows API is defined in the parent class Relation.
 * isBadVersion(version: number): boolean {
 *     ...
 * };
 */

var solution = function(isBadVersion: any) {
    return function(n: number): number {
        
        let minVersion = 0
        // 检查中间的版本是否是错误的
        const checkMiddle = (start: number, end: number): {m: number, isFail: boolean} => {
            const m = Math.floor((end - start)/2) + start
            return {m,isFail: isBadVersion(m)}
        }

        let start = 1,end = n
        while(end >= start) {
            const {m, isFail} = checkMiddle(start,end)
            if (isFail) {
                minVersion = m 
                end = m - 1
            } else {
                start = m + 1

            }
        }

        return minVersion
    };
};

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

二分法(TS):第一个错误的版本

转载自:https://juejin.cn/post/7311274792715993124
评论
请登录