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

This article shows you how to deal with numbers that appear only once in leetcode136. The content is concise and easy to understand. It will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

The standard of "good" algorithm

For the algorithm of a problem, the reason why it is called algorithm, first of all, it must be able to solve the problem (called accuracy). Second, programs written through this algorithm are required not to crash under any circumstances (called robustness). If accuracy and robustness are satisfied, then consider the most important point: the efficiency of the program written through the algorithm.

Operational efficiency is reflected in two aspects:

The running time of the algorithm. (called "time complexity")

The amount of memory required to run the algorithm. (called "space complexity")

The standard of a good algorithm is: on the basis of meeting the requirements of the algorithm itself, the program written by the algorithm runs for a short time and occupies less memory space, so the algorithm can be called a "good algorithm".

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.

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

Example 1: input: [2pr 2pm 1] output: 1

Example 2: input: [4, 1, 2, 2, 2] output: 4

Answer to the question

Train of thought

Use extra HashMap to store each array element, and finally take out the one with the number of 1 (see the topic, there is really no good idea, this method must be very inefficient)

Code implementation

Class Solution {public int singleNumber (int [] nums) {Map temp = new HashMap (); for (int I: nums) {temp.put (I, temp.get (I) = = null? 1: temp.get (I) + 1) } for (int I: nums) {if (temp.get (I) = = 1) {return I;}} return 0;}}

Complexity analysis

Time complexity: O (n) = O (n). The time complexity of the for loop is O (n).

Space complexity: O (n). The space required by hashmap is equal to the number of elements in nums.

Execution result

Optimal solution: bit operation

Train of thought

Any number that is different from 0 or is itself: 0 ^ n = > n

The same number XOR is 0: n ^ n = > 0

XOR satisfies the commutative law and the associative law: a ^ b ^ a = (a ^ a) ^ b = 0 ^ b = b

So we just need to XOR all the numbers to get that unique number.

Code implementation

Class Solution {public int singleNumber (int [] nums) {int result = 0; for (int I: nums) {result ^ = I;} return result;}}

Complexity analysis

Time complexity: O (n). You only need to traverse the nums elements once, so the time complexity is the number of elements in the nums.

Space complexity: O (1).

Execution result

The above is how to deal with the numbers that appear only once in leetcode136. Have you learned the knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

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.