推 pandix: 挖 大師 02/21 04:33
推 shiliuye: 嗯嗯 02/21 04:57
推 NTUEE2CS: 大師 02/21 05:05
推 SecondRun: ：O 02/21 07:19
推 JIWP: 大師 02/21 08:18
※ 引述《pandix (麵包屌)》之銘言：
: 延伸就是像前一篇用 XOR
: 可以發現排完後 i == nums[i] 只有一組會是 (少掉的數字k, n)
: 用 a^a == 0, a^0 == a 的性質就可以把全部的 index/value XOR 起來
: 最後剩下的數字就會是 k^n
: 再 XOR n 就會是 k 了
: 所以也不用換位置那麼麻煩直接 XOR 就好
a XOR a = 0 的這個性質叫做 involution :)
順帶一提, 1 XOR 2 XOR 3 XOR ... XOR n 有 O(1) 的算法
做法是 4 個一組, (0, 1, 2, 3) (4, 5, 6, 7), ...
會發現每一組都會是
xxxxxxx00
xxxxxxx01
xxxxxxx10
xxxxxxx11
的形式，所以四個 XOR 起來就是 0
因此 1 XOR ... XOR n 的結果就可以寫成
n % 4 == 0 --> n
n % 4 == 1 --> 1
n % 4 == 2 --> n + 1
n % 4 == 3 --> 0
:)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.77.61.242 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1708460430.A.7F8.html