LeetCode#136 | Single Number 只出現一次的數字

• 2020 年 3 月 10 日
• 筆記

一、題目

給定一個非空整數數組，除了某個元素只出現一次以外，其餘每個元素均出現兩次。找出那個只出現了一次的元素。

說明：你的演算法應該具有線性時間複雜度。你可以不使用額外空間來實現嗎？

Given an array of integers, every element appears twice except for one. Find that single one.
Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:
Input: [2,2,1]
Output: 1

Example 1:
Input: [4,1,2,1,2]
Output: 4

二、題解

• 解法1：PHP自帶函數 array_count_values()

PHP 的 array_count_values() 函數可以用於統計數組中所有值出現的次數。返回的結果也是一個數組，key 為數組中的元素，value 為該元素出現的次數。

function singleNumber($nums) {      $valueCnt = array_count_values($nums);      return array_search(1, $valueCnt) !== false ? array_search(1, $valueCnt) : false;  }

• 解法2：哈希表

設置一個哈希數組，遍歷給定數組的元素，如果該元素不在哈希表裡，就將該元素放入哈希表中，反之，則將該元素從哈希表中移除。最後哈希表剩下的元素肯定只有一個，則為所求解。但這個不滿足條件中提到的「不使用額外空間」。
時間複雜度：O(n)，空間複雜度：O(n)

function singleNumber($nums) {      $arr = [];      foreach ($nums as $num) {          if (!in_array($num, $arr)) {              $arr[] = $num;          } else {              array_splice($arr, array_search($num, $arr), 1);          }      }      return $arr[0];  }

• 解法3：異或

這個是看了題解才知道還有這麼簡單的方法！很久沒用「異或」這個位運算符了。

對 0 和二進位位做 XOR 運算，得到的仍然是這個二進位位；  對相同的二進位位做 XOR 運算，返回的結果是 0；

時間複雜度：O(1)，空間複雜度：O(n)

function singleNumber($nums) {      $ans = 0;      foreach ($nums as $num) {          $ans = $ans ^ $num;      }      return $ans;  }

運算過程如下：
ans = 0，num = 3：0 ^ 3 = 0 ^ 11(二進位) = 11(二進位) = 3(十進位)；
ans = 3，num = 1：3 ^ 1 = 11(二進位) ^ 1 = 10(二進位) = 2(十進位)；
ans = 2，num = 1：2 ^ 1 = 10(二進位) ^ 1 = 11(二進位) = 3(十進位)；
ans = 3，num = 2：3 ^ 2 = 11 ^ 10(二進位) = 01(二進位) = 1(十進位)；
ans = 1，num = 3：1 ^ 3 = 1 ^ 11(二進位) = 10(二進位) = 2(十進位)。