出租车号码是一个整数，可以用两种不同的方式表示为两个整数立方的和：a^3+b^3 = c^3+d^3. 设计一个算法来找出所有 a、b、c 和 d 小于 N 的出租车号码。
请给出 N 的空间复杂度和时间复杂度。我可以在空间中o(N^2.logN)及时完成O(N^2)。
迄今为止我发现的最佳算法：
形成所有对：N^2
对总和进行排序：N^2 logN
查找小于 N 的重复项
但这需要N^2空间。我们能做得更好吗？
问问题
9811 次
9 回答
27
但这需要 N^2 空间。我们能做得更好吗？
存在基于优先级队列的O(N) 空间解决方案。时间复杂度为O(N^2 logN)。为了勾勒出算法的思想，这里是矩阵 M 使得 M[i][j] = i^3 + j^3 （当然，矩阵永远不会在内存中创建）：
0 1 8 27 64 125
1 2 9 28 65 126
8 9 16 35 72 133
27 28 35 54 91 152
64 65 72 91 128 189
125 126 133 152 189 250
观察每一行和每一行都按升序排序。令 PQ 为优先队列。首先，我们将最大的元素放入优先队列。然后执行以下操作，只要 PQ 不为空：
- 从PQ中弹出最大的元素
- 如果 PQ 没有该行中的任何元素，则在上面添加相邻元素
- 如果 PQ 没有来自该列的任何元素，并且它不在矩阵的对角线下方，则在左侧添加相邻元素（以避免冗余元素）
注意
- 您不需要在内存中创建矩阵来实现算法
- 元素将按降序从 PQ 中弹出，从矩阵的最大元素到最小的元素（避免来自矩阵冗余半部分的元素）。
每次 PQ 发出两次相同的值时，我们就找到了出租车号码。
作为说明，这里是 C++ 中的一个实现。时间复杂度为 O ( N^2 logN)，空间复杂度为 O(N)。
#include <iostream>
#include <cassert>
#include <queue>
using namespace std;
typedef unsigned int value_type;
struct Square
{
value_type i;
value_type j;
value_type sum_of_cubes;
Square(value_type i, value_type j) : i(i), j(j), sum_of_cubes(i*i*i+j*j*j) {}
friend class SquareCompare;
bool taxicab(const Square& sq) const
{
return sum_of_cubes == sq.sum_of_cubes && i != sq.i && i != sq.j;
}
friend ostream& operator<<(ostream& os, const Square& sq);
};
class SquareCompare
{
public:
bool operator()(const Square& a, const Square& b)
{
return a.sum_of_cubes < b.sum_of_cubes;
}
};
ostream& operator<<(ostream& os, const Square& sq)
{
return os << sq.i << "^3 + " << sq.j << "^3 = " << sq.sum_of_cubes;
}
int main()
{
const value_type N=2001;
value_type count = 0;
bool in_i [N];
bool in_j [N];
for (value_type i=0; i<N; i++) {
in_i[i] = false;
in_j[i] = false;
}
priority_queue<Square, vector<Square>, SquareCompare> p_queue;
p_queue.push(Square(N-1, N-1));
in_i[N-1] = true;
in_j[N-1] = true;
while(!p_queue.empty()) {
Square sq = p_queue.top();
p_queue.pop();
in_i[sq.i] = false;
in_j[sq.j] = false;
// cout << "pop " << sq.i << " " << sq.j << endl;
if (sq.i > 0 && !in_i[sq.i - 1] && sq.i-1 >= sq.j) {
p_queue.push(Square(sq.i-1, sq.j));
in_i[sq.i-1] = true;
in_j[sq.j] = true;
// cout << "push " << sq.i-1 << " " << sq.j << endl;
}
if (sq.j > 0 && !in_j[sq.j-1] && sq.i >= sq.j - 1) {
p_queue.push(Square(sq.i, sq.j-1));
in_i[sq.i] = true;
in_j[sq.j - 1] = true;
// cout << "push " << sq.i << " " << sq.j-1 << endl;
}
if (sq.taxicab(p_queue.top())) {
/* taxicab number */
cout << sq << " " << p_queue.top() << endl;
count++;
}
}
cout << endl;
cout << "there are " << count << " taxicab numbers with a, b, c, d < " << N << endl;
return 0;
}
于 2014-05-14T15:03:14.740 回答
15
Novneet Nov 和 user3017842 给出的答案都是使用 minHeap 找到存储 O(N) 的出租车号码的正确想法。再解释一下为什么大小为 N 的 minHeap 有效。首先，如果你有所有的和 (O(N^2)) 并且可以对它们进行排序 (O(N^2lgN))，你只需在遍历排序数组时选择重复项。好吧，在我们使用 minHeap 的例子中，我们可以按顺序遍历所有总和：我们只需要确保 minHeap 始终包含最小的未处理总和。
现在，我们有大量的和 (O(N^2))。但是，请注意，这个数字可以分成 N 组，每组都有一个易于定义的最小值！（修复a，b从0 to N-1=> 更改这里是您的N组。一组中较小的总和小于同一组中b较大的总和b- 因为a是相同的）。
这些组的最小联合是这些组的分钟的联合。因此，如果您将这些组的所有最小值保留在 minHeap 中，则可以保证在 minHeap 中具有总最小值。
现在，当您从堆中提取 Min 时，您只需从该提取的 min 的组中添加下一个最小元素（因此，如果您提取了(a, b)add (a, b+1)）并且您可以保证您的 minHeap 仍然包含所有总和的下一个未处理的 min 。
于 2015-02-19T10:30:41.040 回答
10
我在这里找到了解决方案/代码：时间复杂度 O(N^2 logN)，空间复杂度 O(N) 该解决方案是借助优先级队列实现的。
通过查看代码可以轻松完成逆向思考。它可以在大小为 N 的数组中完成，因为在与下一个最小值比较后，从数组中删除最小和，然后通过添加新的和 - (i^3 + (j+1) 使数组的大小为 N ^3)。
一个直观的证明在这里：
最初，我们在最小优先级队列中添加了 (1,1),(2,2),(3,3),...,(N,N)。
假设 a^+b^3=c^3+d^3，并且 (a,b) 是接下来将从优先级队列中取出的最小值。为了能够检测到这个出租车号码，(c,d) 还必须在优先队列中，该队列将在 (a,b) 之后取出。
注意：我们将在提取 (a,b) 之后添加 (a,b+1)，因此提取 (a,b) 不会导致将 (c,d) 添加到优先级队列中，所以它必须已经存在于优先级队列中。
现在让我们假设 (c,d) 不在优先级队列中，因为我们还没有得到它。相反，优先级队列中有一些 (c,d-k)，其中 k>0。
由于正在取出(a,b)，所以a^3+b^3≤c^3+(d−k)^3
但是，a^3+b^3=c^3+d^3
所以，
c^3+d^3≤c^3+(d−k)^3 d≤d−k k≤0
由于k>0，这是不可能的。因此，我们的假设永远不会实现。因此，对于从 min-PQ 中删除的每个 (a,b)，如果 a^3+b^3=c^3+d，则 (c,d) 已经在 min-PQ 中（或刚刚被删除） ^3
于 2014-07-23T21:12:05.200 回答
8
在任何情况下，算法的时间复杂度都不能小于O(N 2 )，因为您最多可以打印O(N 2 )出租车号码。
为了减少空间使用，理论上你可以使用这里提到的建议：little link。基本上，这个想法是首先你尝试所有可能的对a、b并找到解决方案：
a = 1 - (p - 3 * q)(p 2 + 3 * q 2 )
b = -1 + (p + 3 * q)(p 2 + 3q 2 )
然后，您可以使用以下命令找到合适的c、d对：
c = (p + 3 * q) - (p 2 + 3 * q 2 )
d = -(p - 3 * q) + (p 2 + 3 * q 2 )
并检查它们是否都小于 N。这里的问题是求解该方程组可能会有点混乱（“有点”我的意思是非常乏味）。
O(N 2 )空间解决方案要简单得多，并且可能足够高效，因为可以在合理的时间限制内运行的任何二次时间复杂度都可能适用于二次空间使用。
我希望这有帮助！
于 2012-09-03T08:46:57.617 回答
3
version1 使用 List 并排序
O(n^2*logn) 时间和 O(n^2) 空间
public static void Taxicab1(int n)
{
// O(n^2) time and O(n^2) space
var list = new List<int>();
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
list.Add(i * i * i + j * j * j);
}
}
// O(n^2*log(n^2)) time
list.Sort();
// O(n^2) time
int prev = -1;
foreach (var next in list)
{
if (prev == next)
{
Console.WriteLine(prev);
}
prev = next;
}
}
version2 使用 HashSet
O(n^2) 时间和 O(n^2) 空间
public static void Taxicab2(int n)
{
// O(n^2) time and O(n^2) space
var set = new HashSet<int>();
for (int i = 1; i <= n; i++)
{
for (int j = i; j <= n; j++)
{
int x = i * i * i + j * j * j;
if (!set.Add(x))
{
Console.WriteLine(x);
}
}
}
}
version3 使用面向最小值的优先级队列
O(n^2*logn) 时间和 O(n) 空间
public static void Taxicab3(int n)
{
// O(n) time and O(n) space
var pq = new MinPQ<SumOfCubes>();
for (int i = 1; i <= n; i++)
{
pq.Push(new SumOfCubes(i, i));
}
// O(n^2*logn) time
var sentinel = new SumOfCubes(0, 0);
while (pq.Count > 0)
{
var current = pq.Pop();
if (current.Result == sentinel.Result)
Console.WriteLine($"{sentinel.A}^3+{sentinel.B}^3 = {current.A}^3+{current.B}^3 = {current.Result}");
if (current.B <= n)
pq.Push(new SumOfCubes(current.A, current.B + 1));
sentinel = current;
}
}
SummOfCubes 在哪里
public class SumOfCubes : IComparable<SumOfCubes>
{
public int A { get; private set; }
public int B { get; private set; }
public int Result { get; private set; }
public SumOfCubes(int a, int b)
{
A = a;
B = b;
Result = a * a * a + b * b * b;
}
public int CompareTo(SumOfCubes other)
{
return Result.CompareTo(other.Result);
}
}
于 2017-07-11T15:02:46.420 回答
2
- 创建一个数组：1^3, 2^3, 3^3, 4^3, .... k^3。这样 k^3 < N 和 (k+1)^3 > N。数组大小将是 ~ (N)^(1/3)。数组是排序的。
- 在与数组大小成正比的线性时间内使用 2sum 技术（链接）。如果我们找到 2 对数字，那就是成功。
- 通过每次将 N 减 1 来循环第 2 步。
这将使用 O(N^(1/3)) 额外空间和 ~ O(N^(4/3)) 时间。
于 2014-07-10T23:40:10.080 回答
1
理解时间复杂度 O(N^2 logN)、空间复杂度 O(N)的一种简单方法是将其视为已N排序数组的合并加上先前合并元素的簿记。
于 2016-02-21T06:11:10.383 回答
0
看起来像一个具有适当界限的简单蛮力算法在与n^1.33成正比的时间和与n成正比的空间解决它。或者谁能指出我错的地方？
考虑 4 个嵌套循环，每个循环从 1 运行到n 的三次根。使用这些循环，我们可以遍历 4 个值的所有可能组合，并找到形成出租车号码的对。这意味着每个循环所花费的时间与n 的三次根或n^(1/3)成正比。将该值乘以 4 次，得到：
(n^(1/3)^4 = n^(4/3) = n^1.33
我用 JavaScript 编写了一个解决方案并对其进行了基准测试，它似乎正在工作。一个警告是结果只是部分排序的。
这是我的 JavaScript 代码（它还不是最优的，可以进一步优化）：
function taxicab(n) {
let a = 1, b = 1, c = 1, d = 1,
cubeA = a**3 + b**3,
cubeB = c**3 + d**3,
results = [];
while (cubeA < n) { // loop over a
while (cubeA < n) { // loop over b
// avoid running nested loops if this number is already in results
if (results.indexOf(cubeA) === -1) {
while (cubeB <= cubeA) { // loop over c
while (cubeB <= cubeA) { // loop over d
if (cubeB === cubeA && a!=c && a!=d) { // found a taxicab number!
results.push(cubeA);
}
d++;
cubeB = c**3 + d**3;
} // end loop over d
c++;
d = c;
cubeB = c**3 + d**3;
} // end loop over c
}
b++;
cubeA = a**3 + b**3;
c = d = 1;
cubeB = c**3 + d**3;
} // end loop over d
a++;
b = a;
cubeA = a**3 + b**3;
} // end loop over a
return results;
}
在浏览器控制台中运行taxicab(1E8)大约需要 30 秒，结果会产生 485 个数字。十倍小的值taxicab(1E7)（1000 万）几乎需要 1.4 秒并产生 150 个数字。10^1.33 * 1.4 = 29.9，即n乘以10会导致运行时间增加10^1.33倍。结果数组是未排序的，但在快速排序后，我们得到了正确的结果，如下所示：
[1729, 4104, 13832, 20683, 32832, 39312, 40033, 46683, 64232, 65728,
110656, 110808, 134379, 149389, 165464, 171288, 195841, 216027, 216125,
262656, 314496, 320264, 327763, 373464, 402597, 439101, 443889, 513000,
513856, 515375, 525824, 558441, 593047, 684019, 704977, 805688, 842751,
885248, 886464, 920673, 955016, 984067, 994688, 1009736, 1016496, 1061424,
1073375, 1075032, 1080891, 1092728, 1195112, 1260441, 1323712, 1331064,
1370304, 1407672, 1533357, 1566728, 1609272, 1728216, 1729000, 1734264,
1774656, 1845649, 2048391, 2101248, 2301299, 2418271, 2515968, 2562112,
2585375, 2622104, 2691451, 2864288, 2987712, 2991816, 3220776, 3242197,
3375001, 3375008, 3511872, 3512808, 3551112, 3587409, 3628233, 3798613,
3813992, 4033503, 4104000, 4110848, 4123000, 4174281, 4206592, 4342914,
4467528, 4505949, 4511808, 4607064, 4624776, 4673088, …]
这是基准测试的代码：
// run taxicab(n) for k trials and return the average running time
function benchmark(n, k) {
let t = 0;
k = k || 1; // how many times to repeat the trial to get an averaged result
for(let i = 0; i < k; i++) {
let t1 = new Date();
taxicab(n);
let t2 = new Date();
t += t2 - t1;
}
return Math.round(t/k);
}
最后，我测试了它：
let T = benchmark(1E7, 3); // 1376 - running time for n = 10 million
let T2 = benchmark(2E7, 3);// 4821 - running time for n = 20 million
let powerLaw = Math.log2(T2/T); // 1.3206693816701993
所以这意味着在这个测试中时间与n^1.32成正比。用不同的值重复这个多次总是会产生大致相同的结果：从1.3到1.4。
于 2018-06-20T14:02:28.753 回答
0
首先，我们将构建出租车号码而不是搜索它们。我们将用于构建出租车号码的范围即Ta(2)会上升到n^1/3not n。因为如果你对一个大于n^1/3它的数字进行立方运算，它将大于n，而且我们也不能对负数进行立方运算，以根据定义防止这种情况。我们将使用 HashSet 来记住算法中两个立方数的和。这将帮助我们O(1)在我之前提到的范围内迭代每对可能的数字时及时查找以前的立方和。
时间复杂度：O(n^2/3)
空间复杂度：O(n^1/3)
def taxicab_numbers(n: int) -> list[int]:
taxicab_numbers = []
max_num = math.floor(n ** (1. / 3.))
seen_sums = set()
for i in range(1, max_num + 1):
for j in range(i, max_num + 1):
cube_sum = i ** 3 + j ** 3
if cube_sum in seen_sums:
taxicab_numbers.append(cube_sum)
else:
seen_sums.add(cube_sum)
return taxicab_numbers
于 2021-05-23T19:17:38.500 回答