通过数组的最小异或路由的可能线性时间算法
Possible linear time algorithm for minimum xor route through array
我在一家大公司的技术面试中被问到这个问题。
我可以得到一个基本的暴力破解解决方案，但被要求找到一个更好的解决方案 (O(n))，因为 n 被告知在 5,00,000 的限制内。
给定一个正数整数数组 (p1,p2,.. pn)，任务是找到从第一个数到最后一个数的最小成本路径。路由成本定义为通过数组的 XOR 的总和。例如，如果路由是 p1、p4、p6、p10，则路由成本是 (p1 xor p4) + (p4 xor p6) + (p6 xor p10)。允许重新访问任何数字。我们必须找到从 p1 到 pn 的最小成本路径。 (n<5,00,000)
我只能给出一个暴力解决方案，但它看起来很幼稚。面试官不断要求一些更好的解决方案。我正在考虑一些贪婪的方法，但无法找到解决方案。你能帮我么。
我们有三角不等式
(a XOR b) <= (a XOR c) + (c XOR b) for all a, b, c >= 0,
这可以通过对位位置求和或通过观察我们可以将 XOR 作为度量嵌入 L1 space 中直接证明，其中对应于 [= 的点的第 i 维如果a的二进制表示中对应的位是1，则12=]是2^i，如果对应的位是0.[=18，则0 =]
因此，最佳路径从第一个元素直达最后一个元素，没有中间停靠点。
我在一家大公司的技术面试中被问到这个问题。 我可以得到一个基本的暴力破解解决方案，但被要求找到一个更好的解决方案 (O(n))，因为 n 被告知在 5,00,000 的限制内。
给定一个正数整数数组 (p1,p2,.. pn)，任务是找到从第一个数到最后一个数的最小成本路径。路由成本定义为通过数组的 XOR 的总和。例如，如果路由是 p1、p4、p6、p10，则路由成本是 (p1 xor p4) + (p4 xor p6) + (p6 xor p10)。允许重新访问任何数字。我们必须找到从 p1 到 pn 的最小成本路径。 (n<5,00,000)
我只能给出一个暴力解决方案，但它看起来很幼稚。面试官不断要求一些更好的解决方案。我正在考虑一些贪婪的方法，但无法找到解决方案。你能帮我么。
我们有三角不等式
(a XOR b) <= (a XOR c) + (c XOR b) for all a, b, c >= 0,
这可以通过对位位置求和或通过观察我们可以将 XOR 作为度量嵌入 L1 space 中直接证明，其中对应于 [= 的点的第 i 维如果a的二进制表示中对应的位是1，则12=]是2^i，如果对应的位是0.[=18，则0 =]
因此，最佳路径从第一个元素直达最后一个元素，没有中间停靠点。