题目
给定方程f和值z，找出给定方程f(x,y)=z的正整数解x,y。f(x,y)关于x、y都是严格单调的。
题目保证 f(x, y) == z 的解处于 1 <= x, y <= 1000 的范围内。
方案
暴力双层循环O(N*N)
暴力，双层循环遍历，由于f是单调的，所以一旦遇到大于，则break。同样遇到等于，也可以加入结果并break。时间复杂度O(N*N),N是最大值1000.
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> res=new ArrayList<>();
int MAX_VAL=1000;
for (int i = 1; i <=MAX_VAL ; i++) {
for (int j = 1; j <= MAX_VAL; j++) {
int cul=customfunction.f(i,j);
if(cul==z){
List<Integer> list=new ArrayList<>(2);
list.add(i);
list.add(j);
res.add(list);
break;
}else if(cul>z){
break;
}
}
}
return res;
}
单层循环+二分搜索O(NlogN）
可以一层for+一个二分搜索
由于已知x，y的范围，并且函数单调，则可以用二分。对每个x，尝试二分查找对应的y。O(NlogN)
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> res = new ArrayList<>();
int MAX_VAL = 1000;
for (int i = 1; i <= MAX_VAL; i++) {
int j = binarySearch(1, MAX_VAL, customfunction, z, i);
if (j != -1) {
List<Integer> list = new ArrayList<>(2);
list.add(i);
list.add(j);
res.add(list);
}
}
return res;
}
private int binarySearch(int start, int end, CustomFunction customfunction, int z, int i) {
int left = start;
int right = end;
while (left <= right) {
int mid = (left + right) / 2;
int tmpres = customfunction.f(i, mid);
if (tmpres == z) {
return mid;
} else if (tmpres < z) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
双指针O(N)
可以用双指针。
类似矩阵的方法：
从左下角或者右上角找。选择从左下角找，如果f(x,y)<z，则要走向更大值，需要y++想右；如果大于，则需要向上（x--).如果等于，就需要两个方向都要尝试，往任意一个方向都可以。
public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
List<List<Integer>> res = new ArrayList<>();
int x=1000,y=1;
while(x>=1&&y<=1000){
int tmp=customfunction.f(x,y);
if(tmp<z){
y++;
}else if(tmp>z){
x--;
}else{
List<Integer> list = new ArrayList<>(2);
list.add(x);
list.add(y);
res.add(list);
x--;
}
}
return res;
}
为什么往任意一个方向都可以而不会漏掉？可以类比到矩阵中，如果出现等于，
12345
23456
找f(x,y)=4的，如果从左下角开始，找到第一个4，方案1向上、向右能到第二个4；方案2向右、向上到第二个4.所以当相等的时候，无论向哪个方向都能走到所有的目标值而不会漏掉，因为等会还是会根据单调性向另一个方向走。