This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

A number that appears only once

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Example 1

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

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

Second, train of thought analysis

  • At first glance, this question is very familiar, and this is exactly the same problem we have before. And I could have done it in four different ways.
  • Hash, place substitution, hop addressing, and so on. But there are more or less additional variables in between
  • In place transposition we exchanged two bits of data by bit operation. Which one is interesting.
  • Today we’re going to use bits again to solve the problem of non-repeating data. I might sound a little confused. In fact, the problem is fully solved by using the principle of bit operation

Exclusive or operation

  • First of all, we need to understand the calculation rules of the lower bit operation. The bit operation we’re using here isExclusive or operation 。

  • From this property we can sort out a little bit and conclude that 0 or 1 and 0 xor is itself, and then we can get any number xor with 0 xor is itself

x Sunday afternoon 0 = x x \wedge 0=x
  • If identical is false, then any number that we can figure out is xor with ourselves is 0

x Sunday afternoon x = 0 x \wedge x=0
  • Xor itself is only related to the number itself, and the order of xor has nothing to do with the number, that is, with a or before b or with B or with a

x Sunday afternoon a Sunday afternoon b = x Sunday afternoon b Sunday afternoon a x \wedge a \wedge b= x \wedge b \wedge a

Back to the subject

  • Based on the above three conclusions, in combination with the scenario in our problem: only one number is not repeated, the other numbers are in pairs.
  • Because xor has no order, so either way we can rewrite xor as follows, right

x Sunday afternoon a Sunday afternoon a Sunday afternoon b Sunday afternoon b Sunday afternoon c Sunday afternoon c . . . . . z Sunday afternoon z = x x \wedge a \wedge a \wedge b \wedge b \wedge c \wedge c ….. z \wedge z= x
  • So we just xor all the data in the array. The final answer is the one that doesn’t repeat itself

AC code

public int singleNumber(int[] nums) {
    int result = 0;
    for (int i = 0; i < nums.length; i++) {
        result = result ^ nums[i];
    }
    return result;
}
Copy the code
  • The main investigation in this case is the use of xor. Once you understand the bitwise operation code, it’s not hard to implement.

Four,

  • Bit operations are understood as computer languages. To be good at bitwise computing is to master the language of direct communication with computers.
  • Sometimes it turns our operations into computer level response speed

Thanks for the upvote and closing note