Shulou(Shulou.com)06/01 Report--

This article mainly introduces how to find the number that appears only once in leetcode, which has a certain reference value, and interested friends can refer to it. I hope you will gain a lot after reading this article.

Topic link

Https://leetcode-cn.com/problems/single-number/

Topic description

Given a non-empty integer array, each element appears twice except for an element that appears only once. Find out the element that only appeared once.

Description:

Your algorithm should have linear time complexity. Can you do this without using extra space?

Example 1:

Input: [2pyrrine 2pyr1]

Output: 1

Example 2:

Input: [4, 1, 1, 2, 1, 2]

Output: 4

The idea of solving the problem

Tags: bit operation

According to the meaning of the topic, the linear time complexity O (n), it is easy to think of using Hash mapping to calculate, traverse once and get the result, but the space complexity will reach O (n), so you need to use more extra space.

To meet both time complexity and space complexity, it is necessary to mention the XOR of XOR operation, mainly because XOR operation has the following characteristics:

A number and 0 to do XOR operation is equal to itself: a ⊕ 0 = a

A number and its own XOR operation is equal to 0 a ⊕ a = 0

XOR operation satisfies commutative law and associative law: a ⊕ b ⊕ a = (a ⊕ a) ⊕ b = 0 ⊕ b = b

Therefore, on the basis of the above conditions, all the numbers are done or calculated in order, and the final remaining result is the only number.

Time complexity: O (n), space complexity: O (1)

Code

Java version

Class Solution {

Public int singleNumber (int [] nums) {

Int ans = 0

For (int num: nums) {

Ans ^ = num

}

Return ans

}

}

JavaScript version

/ * *

* @ param {number []} nums

* @ return {number}

, /

Var singleNumber = function (nums) {

Let ans = 0

For (const num of nums) {

Ans ^ = num

}

Return ans

}

Drawing and interpretation

Thank you for reading this article carefully. I hope the article "how to find the number that appears only once in leetcode" shared by the editor will be helpful to you. At the same time, I also hope you will support us and pay attention to the industry information channel. More related knowledge is waiting for you to learn!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.