algorithm - 找出所有四元组[a，b，c，d]，其中当1 <= a，b，c或d <= 10000时a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅关注editing this post的一个问题。

3年前关闭。



Improve this question




寻找算法或一些编码提示以找到解决方案
a^3 + b^3 = c^3 + d^3，其中a, b, c and d都在[1 .. 10000]范围内

这是一个面试问题。

我在考虑优先级队列至少要迭代a和b值。一些提示会很棒，将尝试从那里开始。

最佳答案

使用哈希映射存储(cube,(a,b))，可以迭代所有可能的整数对，并在找到映射中所需的多维数据集之和后输出解决方案。

伪代码:

map <- empty hash_map<int,list<pair<int,int>>>
for each a in range(0,10^5):
  for each b in range(a,10^5): //making sure each pair repeats only once
     cube <- a^3 + b^3
     if map.containsKey(cube):
         for each element e in map.get(cube):
            output e.first(), e.last(), a, b //one solution
     else:
         map.put(cube,new list<pair<int,int>>)
     //for both cases, add the just found pair to the relevant list
     map.get(cube).add(cube,new pair(a,b))

该解决方案平均为O(n ^ 2)space(1)和O(n ^ 2 + OUTPUT)时间，其中OUTPUT是输出的大小。

编辑:

所需的空间实际上是O(n^2 logn)，其中n是范围(10 ^ 5)，因为要表示10^5整数，您需要ceil(log_2(10^15)) = 50位。因此，您实际上需要大约500,000,000,000位(+映射和列表的开销)，约为58.2 GB(+开销)。

因为对于大多数计算机来说，这有点太多了-您可能要考虑将数据存储在磁盘上，或者如果您拥有64位计算机-只需将其存储在“内存”中，并让OS和virtual memory系统尽可能地做到这一点。

(1)正如编辑所阐明的，它实际上是O(n^2log(n))空间，但是，如果我们将每个整数存储区作为O(1)(通常是这种情况)，则会得到O(n^2)空间。显然，相同的原理将适用于时间复杂度。

关于algorithm - 找出所有四元组[a，b，c，d]，其中当1 <= a，b，c或d <= 10000时a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3 ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/14454133/