[閒聊] Grind 169

作者: Rushia (みけねこ的鼻屎)   2022-11-18 09:53:26
136. Single Number
給予一個整數陣列裡面的所有數字都出現兩次只有一個數字出現一次,找出這個數字。
題目限制時間複雜度要是線性等級且空間複雜度需是常數等級。
思路:
1.最簡單的作法應該是用一個set記錄所有數字,若當前數字為n且set不存在n就加入n,
否則移除n,最後剩下的數字就是答案,但是因為題目有限制空間複雜度所以不太OK。
2.可以利用位元運算互斥或的特性,因為 a ^ a = 0 且所有數字只會有1或兩個,所以
全部互斥或在一起最後會是只有一個的數字。
JavaCode:
作者: sixB (6B)   2022-11-18 09:57:00
bitwise大師
作者: pandix (麵包屌)   2022-11-18 10:21:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com