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)
更多推荐
Leetcode 136 Single Number
发布评论