LeetCode： Single Number

Question

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Example 1:

Input: nums = [2, 2, 1]

Output: 1

Example 2:

Input: nums = [4, 1, 2, 1, 2]

Output: 4

Example 3:

Input: nums = [1]

Output: 1

---

Solution #1

首先以 sort! 方法將 nums 集合內所有的元素依序排好，這樣做的好處是相同的元素會排在一起。之後只需要ㄧ個一個比對就可以找到單獨的元素了。

def single_number(nums)
  nums.sort!
  i=0
  while i < nums.length
	  if( nums[i] == nums[i+1] )
	  	i = i + 2
	  else
	  	return nums[i]
	  end
  end
end

Solution #2

首先讓 i = 1, 設定為 1 是因為當 nums 集合內只有ㄧ個元素時，會跳過 while迴圈然後回傳 nums 集合內的第一個，同時也是唯一的元素。

而當 nums 集合規模大於 1 時，會進入 while loop 並且使用 ＾ 符號 XO(exclusive OR) 來逐個的比較元素。 有關 exclusive OR 的概念可參考Wikipedia 的介紹。

基本上是只有當兩個元素都是 false 或是 都是 true 的情況下，才會回傳 false只要有一個 false 或是 true 在任何一方，都是會回傳 true。

true ^ false   => true             false ^ true   => true
true ^ true    => false            false ^ false  => false

以第一個範例 nums = [2, 2, 1] 來說， 當進入 while 迴圈的第一圈時，result = 2 ^ 2 會得到 result = 0。 剛開始我覺得很奇怪為什麼是 0 呢？ 查詢 Ruby手冊 及 bitwise 關鍵字，得知是以位元運算來比較元素的。換句話說，2 ^ 2 其實是這樣：

010 # 2
010 # 2
---
000 # 0

接著跑第二圈時， result = 0 ^ 1 => result = 1。

000 # 0
001 # 1
---
001 # 1

以此類推，就會得到最後的『單獨的數字』

  def single_number(nums)
  i = 1
  result = nums[0]
  while i < nums.length
    result = result ^ nums[i]
	i += 1
  end
  result
end