**subject**

Given an array of integers, every element appears *three* times except for one. Find that single one.

**Note:**

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Given an integer array, each number appears three times (only one number appears only once), to find the number that appears only once. Requirements: time complexity O (n), space complexity O (1). This kind of problem is usually solved by bit operation.

There are 32 bits of 1:int data, which can be stored in 32 variables: the number of “1” on each binary element in the N element. Finally, the “module 3” operation is carried out. If it is 1, then this digit is the 1 digit binary representation.

**CRealization:**

class Solution { public: int singleNumber(int A[], int n) { int bitnum[32]={0}; //Use the bitnum array to save the n elements of the int arrayInt res=0;For (int i=0; i< 32; i++) {For (intJ=0; j< n; j++) {Bitnum[i]+= (A[j]> > I) & 1;Each element in the / / array is taken to 1And operation, and superimpose the result of operation on I number of bitnum array.}Res|= (bitnum[i]%3) < < I; / / will superimpose the result of mode 3 operation to determineBitnum[i]}Return res; / / loop ends, get every element of the bitnum array, and the bitnum array is the element that appears only once.}};

**JAVARealization:**

public class Solution { public int singleNumber(int[] A) { int result = 0; int count = 0; for(int i = 0; i <= 31; i++){ //Each of the bit bits of the loop int typeCount = 0;For (int j = 0; J < = A.length - 1; j++) (/ / meter)The number of I bit bits of all numbers is 1Count + = (A[j] > > I) & 1;}Result = (count% 3) < < I; / / result execution and operation}Return result;}}

Solution 2: This is a faster solution, using three variables to save the distribution of the 1, two, and three times on each binary bit, and finally only to return to the variable one.

class Solution { public: int singleNumber(int A[], int n) { int one=0, two=0, three=0; for(int i=0; i<n; i++){ two |= one&A[i]; one^=A[i]; //cout<<one<<endl; three=one&two; one&= ~three; two&= ~three; } return one; } };

Explanation: each cycle calculates twos first, that is, the distribution of two times 1, then calculates the occurrence of a 1 distribution, and then the two carries out the three distribution of 1, and then inverse to the threes, and then with ones and twos.The purpose of operation is to reset the position three times. This method is faster and more economical, but it is not universal. It

**Similar problems**

Given an array of integers, every element appears** twice** except for one. Find that single one.

**Note:**

*Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?*

class Solution { public: int singleNumber(int A[], int n) { int res=0; for(int i=0;i<n;i++){ res=res^A[i]; } return res; } };

**JavaBit operation**

**Common bit operator**

**1．AND operator**

public class data13

{

public static void main(String[] args)

{

int a=129;

int b=128;

System.out.println(“a And the result of B is: “+ (a& b));

}

}

Running result

a And the results of B are as follows: 128

The following is the analysis of this program:

“a”The value is 129, converted to binary is 10000001, while the value of “B” is 128, and converted to binary is 10000000. According to the operation rule of the operator, only two bits are 1, the result is 1, and we can know that the result is 10000000, that is 128..

**2．OR operator**

The operation rule is as follows: as long as one of the two bits is 1, the result is 1, otherwise it is 0, and the following is a simple example.

public class data14

{

public static void main(String[] args)

{

int a=129;

int b=128;

System.out.println(“a The result of or B is: “+ (a|b)”);

}

}

Running result

a And B or the result is: 129

The following section of this program is analyzed.

a The value is 129, conversion to binary is 10000001, and the value of B is 128, conversion to binary is 10000000, according to or operator’s operation law, only two bits have one is 1, the result is 1, you can know that the result is 10000001, that is 12.9.

**3．NOT operator**

The non operator is represented by the symbol “~”. Its operation rule is as follows: if bit is 0, the result is 1. If bit is 1, the result is 0. Let’s look at a simple example.

public class data15

{

public static void main(String[] args)

{

int a=2;

System.out.println(“a The non – result is: “+ (~a)”);

}

}

**4．XOR operator**

The XOR operator is represented by the symbol “^”. Its operation rule is: the number of two operands is the same, the result is 0, and the difference is 1. Here’s a simple example.

public class data16

{

public static void main(String[] args)

{

int a=15;

int b=2;

System.out.println(“a The result of an alien or B is: “+ (a^b)”);

}

}Running result

a The result with B is: 13

Analysis of the above program section: the value of a is 15, converted to binary to 1111, and the value of B is 2, converted to binary to 0010, according to the rule of abnormal or or, it can be obtained the result is 1101 or 13.