0136._single_number.md

Navigation

• Navigation
• Links:
• Solution 1 异或运算XOR
• Solution 2 数学方法
• Solution 3 哈希表(字典)

Links:

1. https://leetcode.com/problems/single-number/
2. https://leetcode-cn.com/problems/single-number/

Solution 1 异或运算XOR

class Solution:
    def singleNumber(self, nums):
        """
            时间复杂度：O(N)
            空间复杂度：O(1)
        """
        single = 0
        
        for num in nums:
            single ^= num
            
        return single

---

Go

func singleNumber(nums []int) int {
	num := 0

	for _, v := range nums {
		num ^= v
	}

	return num
}

Solution 2 数学方法

class Solution:
    def singleNumber(self, nums):
        """
            时间复杂度：O(N + N) = O(N)。因为sum会调用next去遍历nums。
            空间复杂度：O(N + N) = O(N)
        """
        return 2 * sum(set(nums)) - sum(nums)

---

Go

func singleNumber(nums []int) int {
	m := make(map[int]int, len(nums))

	sum1, sum2 := 0, 0

	for _, v := range nums {
		if _, ok := m[v]; !ok {
			m[v]++
			sum1 += v
		}
		sum2 += v
	}

	return 2*sum1 - sum2
}

Solution 3 哈希表(字典)

class Solution:
    def singleNumber(self, nums):
        """
            时间复杂度：O(N * 1) = O(N)。因为for循环是O(N), dict.pop是O(1)
            空间复杂度：O(N)
        """
        memo = {}

        for num in nums:
            if num not in memo:
                memo[num] = 1
            else:
                memo.pop(num)

        return memo.popitem()[0]

---

class Solution:
    def singleNumber(self, nums):
        memo = {}

        for num in nums:
            try:
                memo.pop(num)
            except:
                memo[num] = 1

        return memo.popitem()[0]

---

Go

func singleNumber(nums []int) int {
	m := make(map[int]int, len(nums))
	for _, v := range nums {
		m[v]++
	}

	for k, v := range m {
		if v == 1 {
			return k
		}
	}

	return 0
}