Leetcode 136 Single Number

Leetcode 136 Single Number"/>

Leetcode 136 Single Number

Leetcode 136 Single Number

题目描述

Given a non-empty 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 2:

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

来源：力扣（LeetCode）
链接：
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路解析

• 思路一

  将列表中所有出现两次的元素均删去，直到列表只含有一个元素或者从尾遍历到头该元素只出现一次，这时直接返回列表的第一个元素即可。代码如下：

class Solution:def singleNumber(self, nums: List[int]) -> int:length = len(nums)j = length - 1while len(nums) != 1:while nums[0] != nums[j]:j -= 1if j == 0:return nums[0]nums.pop(0)nums.pop(j - 1)                j = len(nums) - 1return nums[0]

时间复杂度在最坏的情况下为 O ( N 2 ) O(N^2) O(N2)，空间复杂度为 O ( 1 ) O(1) O(1)

• 异或操作：

异或运算的运算法则为：
a ⊕ a = a a ⊕ 0 = 0 a ⊕ b = b ⊕ a a ⊕ b ⊕ c = ( a ⊕ b ) ⊕ c = a ⊕ ( b ⊕ c ) a\oplus a = a \\ a\oplus 0 = 0 \\ a\oplus b = b\oplus a \\ a\oplus b\oplus c = (a\oplus b) \oplus c=a\oplus(b\oplus c) \\ a⊕a=aa⊕0=0a⊕b=b⊕aa⊕b⊕c=(a⊕b)⊕c=a⊕(b⊕c)
那么用 0 0 0对列表中所有元素做一遍异或，最后得到的值即为只出现一次的元素。代码如下：

class Solution:def singleNumber(self, nums: List[int]) -> int:res = 0for item in nums:res ^= itemreturn res

时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( 1 ) O(1) O(1)

• 哈希表

尝试对列表中的每一个元素建立 元素与1 的键值对，如果哈希表中无此键值对，添加进去；如果已有此键值对，删除哈希表中的键值对。遍历整个列表，最终哈希表中留下的唯一键即为列表中只出现一次的元素。

class Solution:def singleNumber(self, nums: List[int]) -> int:hash_table = {}for item in nums:try:hash_table.pop(item)except:hash_table[item] = 1return hash_table.popitem()[0]

时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( N ) O(N) O(N)

• 数学技巧

class Solution:def singleNumber(self, nums: List[int]) -> int:return 2 * (sum(set(nums))) - sum(nums)                       

时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( N ) O(N) O(N)