Find centralized, trusted content and collaborate around the technologies you use most.
Teams
Q&A for work
Connect and share knowledge within a single location that is structured and easy to search.
如果给定两个数组 A 和 B,每个数组都有 n 个正数和等式:
x^8 = y^6 + x^2y^2 + 10
设计一个在 nlog(n) 时间内运行的算法,在 A 中找到一个 x,在 B 中找到一个 ay,使得前面的等式成立。
首先要做的是对两个数组进行排序,因为我们稍后要使用二进制搜索,但问题是术语
x^2y^2
哪个不能在等式的不同边分开?还是我在这里走错了路?有任何想法吗?
首先要注意的是 x 和 y 都具有偶数幂。这意味着,当您进行排序时,您应该按绝对值排序(仍然是 nlogn)。
然后,遍历array1 的每个元素并对数组2 执行二进制搜索。您应该能够执行二进制搜索,因为该函数是单调递增的。这一步是nlogn。
如果您不理解我的回答,我可以详细说明。
让我知道 :)