找出给定方程的正整数解

难度: Medium

给你一个函数 f(x, y) 和一个目标结果 z，函数公式未知，请你计算方程 f(x,y) == z 所有可能的正整数数对 x 和 y。满足条件的结果数对可以按任意顺序返回。

尽管函数的具体式子未知，但它是单调递增函数，也就是说：

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

函数接口定义如下：

interface CustomFunction {
public:
  // Returns some positive integer f(x, y) for two positive integers x and y based on a formula.
  int f(int x, int y);
};

你的解决方案将按如下规则进行评判：

判题程序有一个由 CustomFunction 的 9 种实现组成的列表，以及一种为特定的 z 生成所有有效数对的答案的方法。
判题程序接受两个输入：function_id（决定使用哪种实现测试你的代码）以及目标结果 z 。
判题程序将会调用你实现的 findSolution 并将你的结果与答案进行比较。
如果你的结果与答案相符，那么解决方案将被视作正确答案，即 Accepted 。

示例 1：

输入：function_id = 1, z = 5
输出：[[1,4],[2,3],[3,2],[4,1]]
解释：function_id = 1 暗含的函数式子为 f(x, y) = x + y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=4 -> f(1, 4) = 1 + 4 = 5
x=2, y=3 -> f(2, 3) = 2 + 3 = 5
x=3, y=2 -> f(3, 2) = 3 + 2 = 5
x=4, y=1 -> f(4, 1) = 4 + 1 = 5

示例 2：

输入：function_id = 2, z = 5
输出：[[1,5],[5,1]]
解释：function_id = 2 暗含的函数式子为 f(x, y) = x * y
以下 x 和 y 满足 f(x, y) 等于 5：
x=1, y=5 -> f(1, 5) = 1 * 5 = 5
x=5, y=1 -> f(5, 1) = 5 * 1 = 5

提示：

1 <= function_id <= 9
1 <= z <= 100
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
在 1 <= x, y <= 1000 的前提下，题目保证 f(x, y) 是一个 32 位有符号整数。

Submission

运行时间: 32 ms

内存: 0.0 MB

"""
   This is the custom function interface.
   You should not implement it, or speculate about its implementation
   class CustomFunction:
       # Returns f(x, y) for any given positive integers x and y.
       # Note that f(x, y) is increasing with respect to both x and y.
       # i.e. f(x, y) < f(x + 1, y), f(x, y) < f(x, y + 1)
       def f(self, x, y):
  
"""
class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        x = 1
        y = 1000
        res = []
        up = 1000
        for y in range(1, 1001):
            x = self.bisec(lambda x: customfunction.f(x, y), 1, up, z)
            if customfunction.f(x, y) == z:
                res.append([x, y])
            elif x == 1:
                break
            up = x
        return res
    
    def bisec(self, f, left, right, z):
        if f(left) >= z:
            return left
        if f(right) == z:
            return right
        while left + 1 < right:
            mid = int((left + right) / 2)
            if f(mid) < z:
                left = mid
            elif f(mid) > z:
                right = mid
            else:
                return mid
        if f(left) >= z:
            return left
        else:
            return right

Explain

题解的思路是使用二分查找配合单调递增的性质来找到满足 f(x, y) == z 的所有整数对 (x, y)。首先固定 y 从 1 到 1000，对于每个 y，使用二分查找在 1 到 1000 的范围内寻找满足条件的 x。如果找到满足条件的 x，则将 (x, y) 添加到结果列表中。为了优化查找过程，每次找到一个解后，将下一次的 x 的搜索上界设置为当前找到的 x，因为函数对于 x 是单调递增的。

时间复杂度: O(m log n)

空间复杂度: O(m)

class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        res = []
        up = 1000
        for y in range(1, 1001):
            x = self.bisec(lambda x: customfunction.f(x, y), 1, up, z)
            if customfunction.f(x, y) == z:
                res.append([x, y])
            elif x == 1:
                break
            up = x
        return res
    
    def bisec(self, f, left, right, z):
        if f(left) >= z:
            return left
        if f(right) == z:
            return right
        while left + 1 < right:
            mid = int((left + right) / 2)
            if f(mid) < z:
                left = mid
            elif f(mid) > z:
                right = mid
            else:
                return mid
        if f(left) >= z:
            return left
        else:
            return right
        # 二分法查找适合的 x 值，适应给定的 y 和 z 条件

Explore

二分查找被选择是因为它比顺序搜索更高效，特别是在数据范围较大时。顺序搜索的时间复杂度为O(n)，而二分查找的时间复杂度为O(log n)，因此在数据范围为1到1000时，二分查找明显更快。相比于插值搜索，二分查找不需要假定数据分布，使其更加通用和稳定，尤其是在未知函数形式或者数据不均匀分布的情况下。

这个范围的设定基于问题的约束和实际情况。假设问题约束了x和y的取值范围在1到1000，这也意味着所有可能的解都位于这个范围内。虽然函数f的具体形式未知，但通常情况下，如果问题设计者提供了这样的范围，那么合理的假设是解应该存在于此范围内。同时，在实际应用中，如果有额外信息表明解可能存在于更广或更窄的范围，那么可以相应调整搜索范围。

在题解中，一旦发现`f(mid) == z`，则直接返回mid作为解。这种做法是基于题目要求找到任意一组满足条件的解，而非所有解。在实际应用中，如果需要找到所有满足条件的x值，应该在找到一个解后继续在左右子区间分别进行搜索，即使当前mid已经满足条件。这需要修改二分查找的实现，以确保不遗漏任何解。

这种方法假设函数f对于x是严格单调递增的。如果函数f在某些y值下对x不是单调递增，或者f在某些区间内对x是常数（即在多个x值上取相同的值），那么设置下一次搜索的上界为当前找到的x可能导致遗漏其他有效的x值。因此，在函数f的单调性未知或不保证时，这种方法可能会失败。