LeetCode 题解:1237. 找出给定方程的正整数解,二分查找,详细注释

原题链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/
解题思路:
根据题意,在给定
x的情况下,y是单调递增的因此,我们可以从
1到1000枚举x,就可以在固定x的情况下,用二分查找搜索y的值如何二分查找:
首先声明左边界
let yLeft = 1,右边界let yRight = 1000计算它们的中间值,
const yMiddle = (yLeft + yRight) >> 1,或者可以用const yMiddle = Math.floor((yLeft + yRight) / 2)如果中间值用函数计算的结果
customfunction.f(x, yMiddle)大于z,说明y的值在yLeft和yMiddle之间,因此可以让yRight = yMiddle - 1,继续在yLeft和yMiddle - 1之间查找y如果中间值用函数计算的结果
customfunction.f(x, yMiddle)小于z,说明y的值在yMiddle和yRight之间,因此可以让yLeft = yMiddle + 1,继续在yRight和yMiddle + 1之间查找y
复制代码
复杂度分析:
时间复杂度:
空间复杂度:。返回值不计入空间复杂度
版权声明: 本文为 InfoQ 作者【Lee Chen】的原创文章。
原文链接:【http://xie.infoq.cn/article/258c055088b07e37ecbce9df3】。文章转载请联系作者。











评论