Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

This is a leetcode problem: a number that appears only once

As a competent rookie, at first sight, of course, the first reaction is good statistical method. Use the dictionary (hash table) to count the number of occurrences of each element, find the number of statistics is 1 element return, kill seconds. Time complexity o(n), space complexity O (n).

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        cntdict ={}
        for n in nums:
            cntdict[n] = cntdict.get(n,0) +1
        for n,cnt in cntdict.items():
            if cnt == 1:
                return n
Copy the code

Just when I was feeling smug, amazed at my talent and speed of thinking, and ready to go to bed, I came across the following request:

I wiped my reading glasses and wondered if I was wrong.

Don’t use extra space

It was as if she had cracked her mouth and laughed at me on screen.

I touched my reading glasses, scratched my recently-thin hair, and started brainstorming:

No extra space? The sorting? Quick sort and see if there’s any repetition in the neighboring elements? Quicksort time complexity O(nlogn), seems inelegant….

	def singleNumber(self, nums: List[int]) -> int:
		nums = sorted(nums)
		i = 0
		while(i<len(nums)-1):
			if nums[i] == nums[i+1]:
				i+=2
			else:
				return nums[i]
		if i == len(nums)-1:
			return nums[i]
Copy the code

As I lay in bed, TOSSING and turning, I began to wonder how to keep my hair from falling out

No, no, no, how do you find an element that only occurs once in linear time without using extra space.

I finally succumbed to my intelligence and clicked the solution

What? Xor? Two lines of code?

Introduction to xOR operations

Xor is a mathematical operator. It applies to logical operations. The mathematical symbol of xOR is ⊕, and the computer symbol is Xor. Binary xOR operation: 1 xor 1=0 0 xor 0=0 1 xor 0=1 0 xor 1=1 In addition, there are:

  1. A ⊕ a is equal to 0
  2. A ⊕ B = B ⊕ A
  3. A ⊕ B ⊕ C = a ⊕ (B ⊕ C) = (a ⊕ B) ⊕ C;
  4. A ⊕ B ⊕ A = B.

So the result of all or all of the elements in this case is the element that only appears once.

	def singleNumber(self, nums: List[int]) -> int:
		sum = 0
		for n in nums:
			sum^=n
		return sum
Copy the code

I cried

A few months later…. Boon? Leetcode daily question seems familiar? I think there’s an awesome solution, right? Student: It looks like we can use bits, right? Oh… Xor, second kill

I touched my Mediterranean and smiled with relief.

Here is a video of my problem solving:

www.bilibili.com/video/BV16g…

Give me a thumbs up for my lost hair