关于面试里算法的空间复杂度的一个问题?

输入:自然数n
输出:一个从小到大的array,array中的元素是a^3+b^3, a和b在自然数[0,n]范围里

要求:时间复杂度O(n^2logn);
空间复杂度O(n)

2个回答

 #include <stdio.h>
#include <stdlib.h>

int cmp(const void *a, const void *b) 
{ 
     return(*(int *)a - *(int *)b);
}

int main()
{
int n;
//scanf("%d", &n);
n = 10;
int* arr = (int *)malloc(n * sizeof(int));
int i = 0;
int x = 0, y = 0;
while (i < n)
{
arr[i] = x * x * x + y * y * y;
if (x == y) { x = 0; y++; } else x++;
i++;
}
// qsort(arr, n, sizeof(int), cmp); 似乎排序是多余的。
for (i = 0; i < n; i++) printf("%d ", arr[i]);
return 0;
}
caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复_1_1_7_: 因为开方在正区间是单调增的,而a,b在我的程序中也是单调增的,所以不需要排序。也就是O(n)的时间复杂度也就可以了。
3 年多之前 回复
u011606457
_1_1_7_ 应该要排序的
3 年多之前 回复

结果
0 1 2 8 9 16 27 28 35 54

caozhy
贵阳老马马善福专业维修游泳池堵漏防水工程 回复dumingyu1992: 是啊,就是提前分配的。
3 年多之前 回复
dumingyu1992
dumingyu1992 回复_1_1_7_: 长度是(n^2+3n+2)/2 但是那样的话空间复杂度是O(n^2)
3 年多之前 回复
u011606457
_1_1_7_ 回复dumingyu1992: Java一样可以的,可以根据n预先算出需要多少空间
3 年多之前 回复
dumingyu1992
dumingyu1992 多谢! 用C/C++写的确避免了空间问题 但如果用java中的array可否达到要求?我想了很久都比不开空间复杂度, 因为java里array需要提前 分配好长度。。。好烦
3 年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!