刷題日記(9)Single Number

Rachel Yeh
1 min readJan 2, 2021

--

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

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

Example 3:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 3 * 104
  • -3 * 104 <= nums[i] <= 3 * 104
  • Each element in the array appears twice except for one element which appears only once.

— — — -(solution中令人歎為觀止超聰明的解法)— — — — —

<Bit Manipulation>

Concept

  • If we take XOR of zero and some bit, it will return that bit
  • a⊕0=a

If we take XOR of two same bits, it will return 0

  • a⊕a=0
  • a⊕b⊕a=(a⊕a)⊕b=0⊕b=b

So we can XOR all bits together to find the unique number.

意思就是只要使用xor最後剩下來的那個就是單獨的那個,因為已經兩兩消除了。

a^=i 是 a= a^i 的意思。

^是XOR

Complexity Analysis

  • Time complexity : O(n). We only iterate through nums, so the time complexity is the number of elements in nums.
  • Space complexity : O(1).

Sign up to discover human stories that deepen your understanding of the world.

Free

Distraction-free reading. No ads.

Organize your knowledge with lists and highlights.

Tell your story. Find your audience.

Membership

Read member-only stories

Support writers you read most

Earn money for your writing

Listen to audio narrations

Read offline with the Medium app

--

--

Rachel Yeh
Rachel Yeh

Written by Rachel Yeh

Taiwan /Software Engineer / Cryptoer

No responses yet

Write a response