题目链接：1237. 找出给定方程的正整数解
方法一：二分查找
解题思路
枚举 \(x\)，然后对 \(y\) 进行二分查找，确定满足 \(customfunction.f(x, y) == z\) 的数对 \((x, y)\)，将其加入 \(ans\) 中，最终返回 \(ans\)。
代码
/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* class CustomFunction {
* public:
* // 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)
* int f(int x, int y);
* };
*/
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int>> ans;
for (int x = 1; x <= 1000; x ++ ) {
int l = 1, r = 1000;
while (l < r) {
if (customfunction.f(x, l) > z || customfunction.f(x, r) < z) break;
int mid = l + r >> 1;
if (customfunction.f(x, mid) >= z) r = mid;
else l = mid + 1;
}
if (customfunction.f(x, l) == z) ans.push_back({x, l});
}
return ans;
}
};
复杂度分析
时间复杂度：\(O(nlogn)\)，\(n\) 为 \(x\) 和 \(y\) 的范围；
空间复杂度：\(O(1)\)。
方法二：相向双指针
解题思路
- 取初始值 \(x = 1, y = 1000\)；
- 对于 \(x = 1\) 相当于在 \([x, 1000]\) 中找寻符合条件的 \(y\)；
- 对于 \(y = 1000\) 相当于在 \([1, y]\) 中找寻符合条件的 \(x\)。
（1）\(f(x, y) = z\) 时，此时将数对 \((x, y)\) 加入 \(ans\) 中，然后找下一对，\(x++\) 或则 \(y--\) 都可以；
（2）\(f(x, y) > z\) 时，由于此时 \(x\) 是能取到的最小值，那么只能缩小 \(y\)，使得 \(f(x, y)\) 减小，即 \(y--\)；
（3）\(f(x, y) < z\) 时，由于此时 \(y\) 是能取到的最大值，那么只能增大 \(x\)，使得 \(f(x, y)\) 增大，即 $ x++$。 - 最后返回 \(ans\)。
代码
/*
* // This is the custom function interface.
* // You should not implement it, or speculate about its implementation
* class CustomFunction {
* public:
* // 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)
* int f(int x, int y);
* };
*/
class Solution {
public:
vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
vector<vector<int>> ans;
int x = 1, y = 1000;
while (x <= 1000 && y >= 1) {
int result = customfunction.f(x, y);
if (result > z) {
y -- ;
} else if (result < z) {
x ++ ;
} else {
ans.push_back({x, y});
x ++ ;
}
}
return ans;
}
};
复杂度分析
时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。