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】。文章转载请联系作者。
评论