上面是題目
要求：時間復雜度為O（n）,空間復雜度為O（1）。
一下是我的代碼：
#include <stdio.h>
int main()
{
int a,b,c,d,i;
char ch;
a=b=c=d=0;
while((ch=getchar())!='\n')
{
if(ch=='a') a++;
else if(ch=='b') b++;
else if(ch=='c') c++;
else if(ch=='d') d++;
}
for(i=0;i<a;i++) printf("a");
for(i=0;i<b;i++) printf("b");
for(i=0;i<c;i++) printf("c");
for(i=0;i<d;i++) printf("d");
printf("\n");
return 0;
}
uj5u.com熱心網友回復：
#include <stdio.h>
#include <string.h>
#include <malloc.h>
int main()
{
int a[4] = { 0 }, i=0;
char ch,*p,*q;
while ((ch = getchar()) != '\n')
a[ch - 'a']++;
q = p = malloc(a[0] + a[1] + a[2] + a[3] + 1);
while (i < 4)
{
memset(q, 'a' + i, a[i]);
q += a[i++];
}
*q = '\0';
puts(p);
free(p);
return 0;
}
前邊半截可以弄短一點，但是后半截不知道資料規模上限不好弄啊。只好想辦法減少輸出次數，只輸出一次試試。
uj5u.com熱心網友回復：
這樣一來空間O(n)了，唉。uj5u.com熱心網友回復：
對，不行，要是能空間O（n）就簡單很多了
uj5u.com熱心網友回復：
問題是你的問題是超時啊。時間空間壓下葫蘆起來瓢這個大家都知道。
你先試試系統是怎么表達空間超標的么。
uj5u.com熱心網友回復：
時間超過會提示時間超時，空間超過會提示記憶體不足
uj5u.com熱心網友回復：
我的意思是我認為系統沒法準確判定你的時空O的級別。uj5u.com熱心網友回復：
這樣試試，供參考：#include <stdio.h>
int main()
{
char b[4]={'a','b','c','d'},ch;
int a[4]={0};
while ((ch = getchar()) != '\n')
a[ch - b[0]]++;
for(int i=0;i<4;i++){
while(a[i]--)
printf("%c",b[i]);
}
system("pause");
return 0;
}
uj5u.com熱心網友回復：
我感覺這個時間復雜度和空間復雜度都超了
uj5u.com熱心網友回復：
這個符合時間復雜度為O（n）,空間復雜度為O（1）。
uj5u.com熱心網友回復：
遍歷一次時間復雜度為O（n)，空間為常數所以復雜度為O（1）。uj5u.com熱心網友回復：
試了，還是超時。
你for里面有個while，是雙重回圈了，還是O（n）嗎，因為還沒學到，只是自己去自學的，所以對時間和空間復雜度不太懂
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/259876.html
標籤：C語言
上一篇：求一元二次方程的根
下一篇：pcl對計算機要求