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

This article mainly introduces how to check the numbers that appear only once in LeetCode. The introduction in the article is very detailed and has a certain reference value. Interested friends must read it!

Title:

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. Your algorithm should have linear time complexity. Can you do this without using extra space?

Train of thought:

Last time I did the sum of two numbers, I was still impressed by hash. When I saw this question, I thought of hash at first sight.

Traverse the array with the current value as key. If the current table contains the number, the value is 2; if not, the value is 1. After traversing, find the number in the table with a value of 1. If it exists, return the corresponding key;. Otherwise, such a number does not exist.

The space complexity is O (n), which does not meet the requirement of not using extra space, but I can't think of any way to cry.

Code: class Solution {public int singleNumber (int [] nums) {/ / given array non-empty Map map = new HashMap (); for (int i:nums) {if (map.containsKey (I)) {map.put (iMagne2) } else map.put (int j:map.keySet 1);} for (int j:map.keySet ()) {if (map.get (j) = = 1) return j;} return-1;}} demo:

Input: [2Jing 2jue 1] output: 1

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

Running result:

Official solution

XOR operation

Property 1: if you do XOR operations on 0 and binary bits, you still get this binary bit.

Property 2: if we do XOR on the same binary bit, the result returned is 0.

Property 3: XOR operations satisfy commutative law and associative law.

Train of thought

Code class Solution {public int singleNumber (int [] nums) {int single = 0; for (int num: nums) {single ^ = num;} return single;}}

Complexity analysis

Time complexity: O (n)

Space complexity: O (1)

Review

Bit operations are not very common, but proper use can greatly reduce overhead.

Bit Operation commonly used in Java

&: bit by bit and.

|: bitwise or.

~: non-by-position.

^: XOR by bit.

Bitwise vs.

Operands 10011 Operand 20101 bitwise and 0001

Bitwise or

Operand 10011 Operand 20101 bitwise or 0111

Bitwise non-

Operand 01 bitwise or 10

Bitwise XOR

Operand 10011 Operand 20101 bitwise or more than 0110 is all the contents of this article "how to check numbers that appear only once in LeetCode". Thank you for reading! Hope to share the content to help you, more related knowledge, 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.