1

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

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

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

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

x^2y^2

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

4

1 回答 1

4

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

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

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

让我知道 :)

于 2013-04-21T06:15:38.527 回答