我在一家大公司的技术面试中被问到这个问题。我可以得到一个基本的蛮力解决方案，但被要求找到一个更好的解决方案(O(n))，因为n被告知在500000的范围内。
给定一个正整数数组(p1,p2，…)Pn)，任务是找到从第一个数字到最后一个数字的最小开销路径。路由开销定义为通过数组的异或值之和。例如，如果路由为p1,p4,p6,p10，则路由开销为(p1 xor p4) + (p4 xor p6) + (p6 xor p10)。允许重新访问任何号码。我们需要找到从p1到pn的最小代价路径。(n<5, 00000)
我只能给出一个解决方案，这是一个蛮力的方法，但它看起来很幼稚。面试官一直在问更好的解决办法。我在考虑一些贪婪的方法，但无法得到解决方案。你能帮帮我吗?
我们有三角形不等式
(a XOR b) <= (a XOR c) + (c XOR b) for all a, b, c >= 0,
可以通过对位位置求和直接证明，或者通过观察我们可以在L1空间中嵌入XOR作为度量，其中a的二进制表示中对应的位为1, 0为0, a对应的点的i维为2^i。
因此，最佳路径从第一个元素直接到最后一个元素，中间没有停止。