写点什么

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

作者:Lee Chen
  • 2023-02-18
    福建
  • 本文字数:878 字

    阅读完需:约 3 分钟

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

原题链接:https://leetcode.cn/problems/find-positive-integer-solution-for-a-given-equation/


解题思路:


  1. 根据题意,在给定x的情况下,y是单调递增的

  2. 因此,我们可以从11000枚举x,就可以在固定x的情况下,用二分查找搜索y的值

  3. 如何二分查找:

  4. 首先声明左边界let yLeft = 1,右边界let yRight = 1000

  5. 计算它们的中间值,const yMiddle = (yLeft + yRight) >> 1,或者可以用const yMiddle = Math.floor((yLeft + yRight) / 2)

  6. 如果中间值用函数计算的结果customfunction.f(x, yMiddle)大于z,说明y的值在yLeftyMiddle之间,因此可以让yRight = yMiddle - 1,继续在yLeftyMiddle - 1之间查找y

  7. 如果中间值用函数计算的结果customfunction.f(x, yMiddle)小于z,说明y的值在yMiddleyRight之间,因此可以让yLeft = yMiddle + 1,继续在yRightyMiddle + 1之间查找y


/** * @param {CustomFunction} customfunction * @param {integer} z * @return {integer[][]} */var findSolution = function(customfunction, z) {  let result = [] // 存储结果
// 枚举所有x for (let x = 1; x <= 1000; x++) { let yLeft = 1 // 二分查找的左边界 let yRight = 1000 // 二分查找的右边界
// 在固定x的前提下,二分查找y的值 while (yLeft <= yRight) { // 取左右边界的中间值 const yMiddle = (yLeft + yRight) >> 1 // 用函数计算中间值的结果 const middleResult = customfunction.f(x, yMiddle)
// 如果结果等于z,这时找到的x和y是是解之一 if (middleResult === z) { result.push([x, yMiddle]) }
// 如果结果大于z,说明y的值在yLeft和yMiddle之间,因此将右边界移动到yMiddle - 1 if (middleResult > z) { yRight = yMiddle - 1 } else { // 如果结果小于z,说明y的值在yMiddle喝yRight之间,因此将左边界移动到yMiddle - 1 yLeft = yMiddle + 1 } } }
return result};
复制代码


复杂度分析:


  • 时间复杂度:

  • 空间复杂度:。返回值不计入空间复杂度

发布于: 刚刚阅读数: 3
用户头像

Lee Chen

关注

还未添加个人签名 2018-08-29 加入

还未添加个人简介

评论

发布
暂无评论
LeetCode题解:1237. 找出给定方程的正整数解,二分查找,详细注释_JavaScript_Lee Chen_InfoQ写作社区