#14658: 時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
學校
:
花蓮縣慈濟大學附中
編號 : 55080
來源 : [59.115.11.142]
最後登入時間 ：
2024-09-04 19:07:03
時間複雜度 O(N)，空間複雜度 O(1)要怎麼做啊？
原本Code：
N>>=1;
long long int ans=(N+1)*N;
long long int A;
N<<=1;
for(int i=0;i<N-1;i++){
cin>>A;
ans-=A;
}
但只能過測資一跟三
有更好的解法嗎？
#14659: Re:時間複雜度 O(N)，空間複雜度 O(1)？
asnewchien@gmail.com
(david)
學校
:
不指定學校
編號 : 68108
來源 : [122.117.95.179]
最後登入時間 ：
2024-11-04 20:21:51
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
#14678: Re:時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
學校
:
花蓮縣慈濟大學附中
編號 : 55080
來源 : [59.115.11.142]
最後登入時間 ：
2024-09-04 19:07:03
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
因為我從測資觀察是這樣
如果這樣的話確實可以把 時間壓到 O(N)，空間 O(1)
但是測資二不是這樣的
所以只好寫 時間 O(NlogN)，空間 O(N) 的寫法了
#14892: Re:時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
學校
:
花蓮縣慈濟大學附中
編號 : 55080
來源 : [59.115.11.142]
最後登入時間 ：
2024-09-04 19:07:03
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
因為我從測資觀察是這樣
如果這樣的話確實可以把 時間壓到 O(N)，空間 O(1)
但是測資二不是這樣的
所以只好寫 時間 O(NlogN)，空間 O(N) 的寫法了
後來發現其實可以壓到空間 O(1)
善用 xor 運算子就可以了ww
ZeroJudge Forum