【每日一题Day122】LC1237找出给定方程的正整数解 | 双指针 二分查找

找出给定方程的正整数解【LC1237】

给你一个函数 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 。

说真的 我看了评论区才看懂题目的

暴力

• 思路：双重循环枚举每个可能的$x$和$y$，通过customfunction.f(x, y)求出运算结果，如果结果等于$z$，那么加入结果集中；由于函数是单调递增函数，因此如果结果大于$z$时，退出循环。

• 实现

  class Solution {public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {List<List<Integer>> res = new ArrayList<>();for (int i = 1; i <= 1000; i++){for (int j = 1; j <= 1000; j++){int num = customfunction.f(i, j);if (num == z){res.add(Arrays.asList(i, j));}else if (num > z){break;}}}return res;}
  }
  

  • 复杂度

    • 时间复杂度：$O(C^2)$，$C$为x和y的取值范围，本题中为$1000$
    • 空间复杂度：$O(1)$

二分查找

• 思路：由于函数为单调递增函数，因此可以固定$x$，二分查找$y$，二分查找的上限为1，下限为1000，假定运算结果为$num$

  • 如果$num==z$，那么将结果添加至结果集
  • 如果$num>z$，那么$y$向左边查询，right = mid - 1
  • 如果$num==z$，那么$y$向右边查询，left = mid + 1

• 实现

  /** // 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)*     public int f(int x, int y);* };*/class Solution {public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {List<List<Integer>> res = new ArrayList<>();for (int i = 1; i <= 1000; i++){int jL = 1, jR = 1000;while (jL <= jR){int mid = (jL + jR) / 2;int num = customfunction.f(i, mid);if (num == z){res.add(Arrays.asList(i, mid));break;}else if (num > z){jR = mid - 1;}else{jL = mid + 1;}}}return res;}
  }
  

  • 复杂度

    • 时间复杂度：$O(ClogC)$，$C$为x和y的取值范围，本题中为$1000$
    • 空间复杂度：$O(1) $

双指针

• 思路：当$x_1<x_2$时，如果$f(x_1,y_1)=f(x_2,y_2)=z$，那么此时$y_1>y_2$，因此可以从小到大枚举$x$，从大到小枚举$y$，那么可以固定$x$，在上次循环的$y$值作为起始值，找到本次的$y$。

• 实现

  class Solution {public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {List<List<Integer>> res = new ArrayList<>();int j = 1000;for (int i = 1; i <= 1000; i++){while (j >= 1 && customfunction.f(i, j) > z){j--;}if (j >= 1 && customfunction.f(i, j) == z){res.add(Arrays.asList(i, j));}}return res;}
  }
  

  • 复杂度

    • 时间复杂度：$O(C)$，$C$为x和y的取值范围，本题中为$1000$
    • 空间复杂度：$O(1) $