1237.找出给定方程的正整数解

链接：1237.找出给定方程的正整数解
难度：Medium
标签：数学、双指针、二分查找、交互
简介：给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。

题解 1 - cpp

• 编辑时间：2023-02-18
• 内存消耗：6.3MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        for (int x = 1; x <= 1000; x++) {
            int l = 1, r = 1000, m;
            while (l <= r) {
                m = (l + r) / 2;
                int val = customfunction.f(x, m);
                if (val == z) {
                    vector<int> item{ x, m };
                    res.push_back(item);
                    break;
                }
                if (val > z) r = m - 1;
                else l = m + 1;
            }
        }
        return res;
    }
  };

题解 2 - python

• 编辑时间：2023-02-18
• 执行用时：148ms
• 内存消耗：14.9MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        res = []
        for x in range(1, 1001):
            l, r = 1, 1000
            while l <= r:
                m = (l + r)//2
                val = customfunction.f(x, m)
                if val == z:
                    res.append([x, m])
                    break
                if val > z:
                    r = m - 1
                else:
                    l = m + 1
        return res

题解 3 - rust

• 编辑时间：2023-02-18
• 执行用时：4ms
• 内存消耗：2.2MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn find_solution(customfunction: &CustomFunction, z: i32) -> Vec<Vec<i32>> {
        let mut res = vec![];
        for x in 1..=1000 {
            let (mut l, mut r) = (1, 1000);
            while l <= r {
                let m = (l + r) / 2;
                let val = customfunction.f(x, m);
                if val == z {
                    res.push(vec![x, m]);
                    break;
                }
                if val > z {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            }
        }
        res
    }
}