Loading...
墨滴

Shinkai005

2021/12/11  阅读:39  主题:红绯

【leetcode】374.猜数字大小

【leetcode】374.猜数字大小

题目描述

image-20211211232150171
image-20211211232150171

题目思路

二分搜索同样具有 "分,解,合"的特性

考虑使用分而治之的思想

个人题解

分: 计算中间元素 分割数组

解:递归地在较大或者是较小数组进行二分搜索

合: 不需要这一步,因为如果搜到结果就直接返回了.

/**
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return                -1 if num is lower than the guess number
 *                         1 if num is higher than the guess number
 *                       otherwise return 0
 * var guess = function(num) {}
 */


/**
 * @param {number} n
 * @return {number}
 */

var guessNumber = function (n{
    const rec = (low, high) => {
        if (low > high) return;
        const mid = Math.floor((low + high) / 2);
        const res = guess(mid);
        if (res === 0) {
            return mid;
        } else if (res === 1) {
            return rec(mid + 1, high)
        } else {
            return rec(1, mid - 1);
        }
    };
    return rec(1, n);
};

总结优化

时间复杂度(time complexity)

O(n)

空间复杂度(space complexity)

O(logN)

Shinkai005

2021/12/11  阅读:39  主题:红绯

作者介绍

Shinkai005