Article From:https://www.cnblogs.com/moonlightml/p/9216619.html

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
   JavaA bit operator is defined for integer type (int), long integer (long), short integer (short), character type (char), and byte type (byte). The bit operator acts on all bits and bit operations. The bit operator is calculated at twoBinary format, that is, if the given number format is not binary format, it needs to be converted to binary format first.
Common bit operator
1.AND operator
With the symbol “&” with the operator, the operator is used as follows: the two operand medium is 1, the result is 1, or the result is 0, for example, the following program section.

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.

Leave a Reply

Your email address will not be published. Required fields are marked *