LeetCode_Single Number

Posted on | In | Views:

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. 哈希表

使用哈希表保存数组，时间复杂度为O(n)，空间复杂度为O(n)。具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        num_dict = {}
         
        for num in nums:
            if num not in num_dict:
                num_dict[num] = 1
            else:  
                 num_dict[num] += 1
        
        for key in num_dict:
            if num_dict[key] == 1:
                return key

2. 按位异或

题中要求使用时间复杂度为O(n)，空间复杂度为O(1)。在遍历数组的过程中使用按位异或的方法，最终会保留下只存在一次的数字。具体实现过程如下：

1
2
3
4
5
6
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        result = 0
        for num in nums:
            result ^=  num
        return result