当前位置：网站首页>Find the number that appears only once in the array

Find the number that appears only once in the array

2022-06-30 09:01:00 【Byte station】

1. subject ( difficult )

Given an array , Except for one element, only 1 Time , All the other elements appear 3 Time . Design an algorithm to find elements that only appear once . The required time complexity is O(n), Extra space O(1).

1.1 Example

Input : arr[] = {12, 1, 12, 3, 12, 1, 1, 2, 3,3}
Output : 2
except 2 Everything else 3 Time .
Input : arr[] = {10, 20, 10, 30, 10, 30, 30}
Output : 20
except 20 Everything else 3 Time .

1.2 java Code implementation

class GFG {
	static int getSingle(int arr[], int n)
	{
		int ones = 0, twos = 0;
		int common_bit_mask;

		for (int i = 0; i < n; i++) {
			twos = twos | (ones & arr[i]);
			ones = ones ^ arr[i];
      
			common_bit_mask = ~(ones & twos);
      
			ones &= common_bit_mask;
			twos &= common_bit_mask;
		}
		return ones;
	}

	public static void main(String args[])
	{
		int arr[] = { 3, 3, 2, 3 };
		int n = arr.length;
		System.out.println(" The element that appears only once is  " + getSingle(arr, n));
	}
}

Output ：

The element that appears only once is 2

2. Algorithm explanation

2.1 Bitwise operation

2.1.1 And (&) Operator ：

a & b Only a、b Also for 1, be a & b = 1.1 & 1 = 1、1 & 0 = 0、0 & 1 = 0、0 & 0 = 0.
effect ： Inquire about , Find the same . Look for two numbers in common 1 Of bit position .

2.1.2 or (|) Operator ：

a | b a、b Any one for 1, be a | b = 1.1 | 1 = 1、1 | 0 = 1、0 | 1 = 1、0 | 0 = 0.
effect ： assignment . take a On And b by 1 Of bit position Corresponding bit The position is 1.

2.1.3 Not (~) Operator

Reverse operation ,~1 = 0,~0 = 1.
effect ： combination & operation eliminate .a &= ~b.

2.1.4 Exclusive or (^)

a ^ b Only ab Mutually exclusive , be a ^ b = 1.1 ^ 0 = 1、0 ^ 1 = 1、0 ^ 0 = 0、1 ^ 1 = 0.
effect ： Inquire about , Make a difference .
shorthand ： Complementation of yin and Yang , Only men and women can have children . Looking at the same pattern in the game repeatedly can offset .

2.2 Their thinking

Record each bit by 1 The number of times . appear 1 Secondary existence ones On . appear 2 Secondary existence twos On . appear 3 Remove... Times .

As the required time complexity is O(n), So loop through the array .
Set two variables ones,twos.ones The meaning is , Elements bit The bit value is 1 appear 1 Time , Assign a value to ones.ones = ones^arr[i]. twos The meaning is ： If the element currently traversed bit The bit value is 1 appear 2 When the time , Assign a value to twos.
If the element currently traversed bit The bit value is 1 There is 3 Time , Will ones and twos The bit The value on the bit is cleared .
Final ones The value of is a number that appears only once .

A few doubts ？

Why? ones Use XOR (^) operation ？

answer ： With { 3, 3, 2, 3 } For example . First traversal ,ones = 3.* Second traversal ,arr[1] =3. ones Need to become 0. Need to offset arr[1]. It's kind of like xiaoxiaole . So use XOR operation .