LeetCode1237找出给定方程的正整数解

题目

给定方程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.所以当相等的时候，无论向哪个方向都能走到所有的目标值而不会漏掉，因为等会还是会根据单调性向另一个方向走。

LeetCode1237找出给定方程的正整数解的相关教程结束。