arrays - 在两个数组中找到方程的解

Question

如果给定两个数组 A 和 B，每个数组都有 n 个正数和等式：

x^8 = y^6 + x^2y^2 + 10

设计一个在 nlog(n) 时间内运行的算法，在 A 中找到一个 x，在 B 中找到一个 ay，使得前面的等式成立。

首先要做的是对两个数组进行排序，因为我们稍后要使用二进制搜索，但问题是术语

x^2y^2

哪个不能在等式的不同边分开？还是我在这里走错了路？有任何想法吗？

Answer 1

首先要注意的是 x 和 y 都具有偶数幂。这意味着，当您进行排序时，您应该按绝对值排序（仍然是 nlogn）。

然后，遍历array1 的每个元素并对数组2 执行二进制搜索。您应该能够执行二进制搜索，因为该函数是单调递增的。这一步是nlogn。

如果您不理解我的回答，我可以详细说明。

让我知道 ：）