[LeetCode] 260. Single Number III

轉自LeetCode

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

Note:

1. The order of the result is not important. So in the above example, [5, 3] is also correct.
2. Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

<Solution>
這題算 Single Number 的衍生

不同的地方在於，這次出現一次的數字不是一個，而是兩個

解題的主要方向還是使用 XOR

想法如下

• 因為其它出現的數字都是出現兩次，所以XOR的結果都會是0

• 而當對所有數字做完XOR後，其結果(用 allXOR 表示)等同於兩個出現一次的數字做XOR

• 而allXOR裡面是1的bits，就是兩個不同數字不重複的bits。這時候，可以透過 allXOR &= -allXOR，來得到 rightmost set bit，因為只需要一個bit，就可以來區分這兩個數字

• 對 nums 再做一次歷遍XOR並利用 rightmost set bit 來做分群，這樣就可以得到答案

code 如下(參考資料)

C++

Kotlin