Re: [閒聊] 每日LeetCode

看板Marginalman作者involution (內卷是好文明)時間3月前 (2024/02/21 04:20)推噓5(5推 0噓 0→)

留言5則, 5人參與討論串701/719 (看更多)

※ 引述《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

推

pandix

02/21 04:33, 3月前 , 1^F

02/21 04:33, 1^F

推

shiliuye

02/21 04:57, 3月前 , 2^F

02/21 04:57, 2^F

推

NTUEE2CS

02/21 05:05, 3月前 , 3^F

02/21 05:05, 3^F