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(十进制)。