#14658: 時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
時間複雜度 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)
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
#14678: Re:時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
因為我從測資觀察是這樣
如果這樣的話確實可以把 時間壓到 O(N)，空間 O(1)
但是測資二不是這樣的
所以只好寫 時間 O(NlogN)，空間 O(N) 的寫法了
#14892: Re:時間複雜度 O(N)，空間複雜度 O(1)？
tico88612
(Kagamine Rin)
你應該誤解題意了，還是我誤解。
A 會是 1 到 n/2 嗎。
因為我從測資觀察是這樣
如果這樣的話確實可以把 時間壓到 O(N)，空間 O(1)
但是測資二不是這樣的
所以只好寫 時間 O(NlogN)，空間 O(N) 的寫法了
後來發現其實可以壓到空間 O(1)
善用 xor 運算子就可以了ww