出租车编号是一个整数,可以用两种不同的方式表示为两个整数立方体的总和: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空间.我们可以做得更好吗？
use*_*842 20
但这需要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发出两次相同的值时,我们就会找到一个出租车编号.
作为说明,这是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;
}
Mar*_*ova 10
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)你的添加(a, b+1)),你保证你的minHeap仍然包含所有总和的下一个未处理的min.
在任何情况下,算法的时间复杂度都不能小于O(N 2),因为您可能会打印多达O(N 2)的出租车编号.
为了减少空间使用,理论上你可以使用这里提到的建议:小链接.基本上,这个想法是首先你尝试所有可能的对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)空间的解决方案要简单得多,它可能会是因为能够在合理的时间限制运行可能会被罚款与二次空间使用二次的时间复杂度什么足够的效率.
我希望有所帮助!
我在这里找到了解决方案/代码:时间复杂度O(N ^ 2 logN),空间复杂度O(N) 该解决方案是通过优先级队列的帮助实现的.
通过查看代码可以轻松完成反向思考.它可以在大小为N的阵列进行,因为最小总和被从阵列比较到下一个最小后通过添加新的总和删除,然后将阵列到大小为N由 - (I ^ 3 +(J + 1) ^ 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)^3d≤d-kk≤0
由于k> 0,这是不可能的.因此,我们的假设永远不会成真.因此,对于从min-PQ中移除的每个(a,b),如果a ^ 3 + b ^ 3 = c ^ 3 + d,则(c,d)已经在min-PQ中(或者刚被移除) ^ 3