1237-找出给定方程的正整数解

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

给你一个函数 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 位有符号整数。

前言

本题是「240. 搜索二维矩阵 II 」的变形题。

方法一：枚举

根据题目给出的 x 和 y 的取值范围，枚举所有的 x, y 数对，保存满足 f(x,y)=z 的数对，最后返回结果。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
# 超时
class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        ans = []
        for x in range(1, 1001):
            for y in range(1, 1001):
                if customfunction.f(x, y) == z:
                    ans.append([x, y])
        return ans
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        for (int x = 1; x <= 1000; x++) {
            for (int y = 1; y <= 1000; y++) {
                if (customfunction.f(x, y) == z) {
                    res.push_back({x, y});
                }
            }
        }
        return res;
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int x = 1; x <= 1000; x++) {
            for (int y = 1; y <= 1000; y++) {
                if (customfunction.f(x, y) == z) {
                    List<Integer> pair = new ArrayList<Integer>();
                    pair.add(x);
                    pair.add(y);
                    res.add(pair);
                }
            }
        }
        return res;
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
        IList<IList<int>> res = new List<IList<int>>();
        for (int x = 1; x <= 1000; x++) {
            for (int y = 1; y <= 1000; y++) {
                if (customfunction.f(x, y) == z) {
                    res.Add(new List<int> {x, y});
                }
            }
        }
        return res;
    }
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int** findSolution(int (*customFunction)(int, int), int z, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * 1000 * 1000);
    int pos = 0;
    for (int x = 1; x <= 1000; x++) {
        for (int y = 1; y <= 1000; y++) {
            if (customFunction(x, y) == z) {
                res[pos] = (int *)malloc(sizeof(int) * 2);
                res[pos][0] = x, res[pos][1] = y;
                pos++;
            }
        }
    }
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return res;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var findSolution = function(customfunction, z) {
    const res = [];
    for (let x = 1; x <= 1000; x++) {
        for (let y = 1; y <= 1000; y++) {
            if (customfunction.f(x, y) === z) {
                res.push([x, y]);
            }
        }
    }
    return res;
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
    for x := 1; x <= 1000; x++ {
        for y := 1; y <= 1000; y++ {
            if customFunction(x, y) == z {
                ans = append(ans, []int{x, y})
            }
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(mn)，其中 m 是 x 的取值数目，n 是 y 的取值数目。

  • 空间复杂度：O(1)。返回值不计入空间复杂度。

方法二：二分查找

当我们固定 x = x_0 时，函数 g(y) = f(x_0, y) 是单调递增函数，可以通过二分查找来判断是否存在 y=y_0，使 g(y_0)=f(x_0,y_0)=z 成立。

[sol2-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        ans = []
        for x in range(1, 1001):
            y = 1 + bisect_left(range(1, 1000), z, key=lambda y: customfunction.f(x, y))
            if customfunction.f(x, y) == z:
                ans.append([x, y])
        return ans
[sol2-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        for (int x = 1; x <= 1000; x++) {
            int yleft = 1, yright = 1000;
            while (yleft <= yright) {
                int ymiddle = (yleft + yright) / 2;
                if (customfunction.f(x, ymiddle) == z) {
                    res.push_back({x, ymiddle});
                    break;
                }
                if (customfunction.f(x, ymiddle) > z) {
                    yright = ymiddle - 1;
                } else {
                    yleft = ymiddle + 1;
                }
            }
        }
        return res;
    }
};
[sol2-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int x = 1; x <= 1000; x++) {
            int yleft = 1, yright = 1000;
            while (yleft <= yright) {
                int ymiddle = (yleft + yright) / 2;
                if (customfunction.f(x, ymiddle) == z) {
                    List<Integer> pair = new ArrayList<Integer>();
                    pair.add(x);
                    pair.add(ymiddle);
                    res.add(pair);
                    break;
                }
                if (customfunction.f(x, ymiddle) > z) {
                    yright = ymiddle - 1;
                } else {
                    yleft = ymiddle + 1;
                }
            }
        }
        return res;
    }
}
[sol2-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
        IList<IList<int>> res = new List<IList<int>>();
        for (int x = 1; x <= 1000; x++) {
            int yleft = 1, yright = 1000;
            while (yleft <= yright) {
                int ymiddle = (yleft + yright) / 2;
                if (customfunction.f(x, ymiddle) == z) {
                    res.Add(new List<int> {x, ymiddle});
                    break;
                }
                if (customfunction.f(x, ymiddle) > z) {
                    yright = ymiddle - 1;
                } else {
                    yleft = ymiddle + 1;
                }
            }
        }
        return res;
    }
}
[sol2-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int** findSolution(int (*customFunction)(int, int), int z, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * 1000 * 1000);
    int pos = 0;
    for (int x = 1; x <= 1000; x++) {
        int yleft = 1, yright = 1000;
        while (yleft <= yright) {
            int ymiddle = (yleft + yright) / 2;
            if (customFunction(x, ymiddle) == z) {
                res[pos] = (int *)malloc(sizeof(int) * 2);
                res[pos][0] = x, res[pos][1] = ymiddle;
                pos++;
                break;
            }
            if (customFunction(x, ymiddle) > z) {
                yright = ymiddle - 1;
            } else {
                yleft = ymiddle + 1;
            }
        }
    }
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return res;
}
[sol2-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var findSolution = function(customfunction, z) {
    const res = [];
    for (let x = 1; x <= 1000; x++) {
        let yleft = 1, yright = 1000;
        while (yleft <= yright) {
            const ymiddle = Math.floor((yleft + yright) / 2);
            if (customfunction.f(x, ymiddle) === z) {
                res.push([x, ymiddle]);
                break;
            }
            if (customfunction.f(x, ymiddle) > z) {
                yright = ymiddle - 1;
            } else {
                yleft = ymiddle + 1;
            }
        }
    }
    return res;
};
[sol2-Golang]
1
2
3
4
5
6
7
8
9
func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
    for x := 1; x <= 1000; x++ {
        y := 1 + sort.Search(999, func(y int) bool { return customFunction(x, y+1) >= z })
        if customFunction(x, y) == z {
            ans = append(ans, []int{x, y})
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(m \log n)，其中 m 是 x 的取值数目，n 是 y 的取值数目。

  • 空间复杂度：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，只需要从上次结束的值开始枚举即可。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def findSolution(self, customfunction: 'CustomFunction', z: int) -> List[List[int]]:
        ans = []
        y = 1000
        for x in range(1, 1001):
            while y and customfunction.f(x, y) > z:
                y -= 1
            if y == 0:
                break
            if customfunction.f(x, y) == z:
                ans.append([x, y])
        return ans
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {
        vector<vector<int>> res;
        for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
            while (y >= 1 && customfunction.f(x, y) > z) {
                y--;
            }
            if (y >= 1 && customfunction.f(x, y) == z) {
                res.push_back({x, y});
            }
        }
        return res;
    }
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> findSolution(CustomFunction customfunction, int z) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
            while (y >= 1 && customfunction.f(x, y) > z) {
                y--;
            }
            if (y >= 1 && customfunction.f(x, y) == z) {
                List<Integer> pair = new ArrayList<Integer>();
                pair.add(x);
                pair.add(y);
                res.add(pair);
            }
        }
        return res;
    }
}
[sol3-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public IList<IList<int>> FindSolution(CustomFunction customfunction, int z) {
        IList<IList<int>> res = new List<IList<int>>();
        for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
            while (y >= 1 && customfunction.f(x, y) > z) {
                y--;
            }
            if (y >= 1 && customfunction.f(x, y) == z) {
                res.Add(new List<int> {x, y});
            }
        }
        return res;
    }
}
[sol3-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int** findSolution(int (*customFunction)(int, int), int z, int* returnSize, int** returnColumnSizes) {
    int **res = (int **)malloc(sizeof(int *) * 1000 * 1000);
    int pos = 0;
    for (int x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
        while (y >= 1 && customFunction(x, y) > z) {
            y--;
        }
        if (y >= 1 && customFunction(x, y) == z) {
            res[pos] = (int *)malloc(sizeof(int) * 2);
            res[pos][0] = x, res[pos][1] = y;
            pos++;
        }
    }
    *returnSize = pos;
    *returnColumnSizes = (int *)malloc(sizeof(int) * pos);
    for (int i = 0; i < pos; i++) {
        (*returnColumnSizes)[i] = 2;
    }
    return res;
}
[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
var findSolution = function(customfunction, z) {
    const res = [];
    for (let x = 1, y = 1000; x <= 1000 && y >= 1; x++) {
        while (y >= 1 && customfunction.f(x, y) > z) {
            y--;
        }
        if (y >= 1 && customfunction.f(x, y) === z) {
            res.push([x, y]);
        }
    }
    return res;
};
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
func findSolution(customFunction func(int, int) int, z int) (ans [][]int) {
    for x, y := 1, 1000; x <= 1000 && y > 0; x++ {
        for y > 0 && customFunction(x, y) > z {
            y--
        }
        if y > 0 && customFunction(x, y) == z {
            ans = append(ans, []int{x, y})
        }
    }
    return
}

复杂度分析

  • 时间复杂度：O(m + n)，其中 m 是 x 的取值数目，n 是 y 的取值数目。

  • 空间复杂度：O(1)。返回值不计入空间复杂度。

 Comments
On this page
1237-找出给定方程的正整数解