Find the single dog (Li Kou 260)

         Preface : Today I bring you the original question , There are many solutions  , Different solutions have different difficulties , So today I will bring you two solutions , Violence and bit operations . One is simple , I medium .

          Only two numbers in an array appear once , All the other numbers came up twice . Write a function to find these two numbers that only appear once .

One . Violence solution :

         Take an extreme case :2 2 4 6 5 8 4 6, First, sort the bubbles :2 2 4 4 5 6 6 8, Then compare the sorted arrays one by one . The time complexity of seemingly simple logic is O(N^2). It can be said that it is very time-consuming . Those who don't understand the time complexity can see that my previous blog has the most time complexity 0 Basic explanation .CSDN

#include<string.h>
#include<errno.h>
void search_signal_dog1(int arr[],int size) {	
	for (int i = 0; i < size-1; i++) {// After bubble sorting :2 2 4 4 5 6 6 8 
		int flag = 1;
		for (int j = 0; j < size-1-i; j++) {
			if (arr[j]> arr[j+1 ]) {
				int tmp = arr[j + 1];
				arr[j + 1] = arr[j];
				arr[j] = tmp;
				flag = 0;
			}
		}
		if (flag == 1) {
			break;
		}
	}
	for (int i = 0; i < size;) {// Just compare directly after sorting 
		if (arr[i] == arr[i + 1]) {
			i += 2;
		}
		else {
			printf("%d\n", arr[i]);
			i++;
		}
	}
	
}
int main() {
	int arr[] = { 2,2,4,6,5,8,4,6 };
	size_t size = sizeof(arr) / sizeof(arr[0]);
	search_signal_dog1(arr,size);

  Two . Method of bit operation :

         First we will [1,2,3,4,5,1,2,3,4,6] Store in an array . among 5 and 6 Is a separate number . If we XOR the entire array , Then the same element XOR is 0, Different elements will become another number after XOR , In this case, the difference is :ret=5^6=3. Then we can know from the characteristics of XOR : The different bits after the XOR of two numbers are 1, The same bit is 0, So we found ret In binary pos Is it 1. Record pos After bits, we iterate through the array , Move in the array pos Bit by bit and 1==1 A set of , It's not equal to 1 A set of . After being divided into two groups , The answer can be obtained by exclusive or of the elements in each group .

void search_signal_dog2(int arr[], int size, int* p1, int* p2) {
	//1. Exclusive or 
	int ret = 0;
	for (int i = 0; i < size; i++) {
		ret ^= arr[i];//5^6
	}
	int pos = 0;
	//2. Calculation ret Which bit of the binary bit of is 1
	for ( pos = 0; pos < 32; pos++) {
		if (((ret >> pos) & 1) == 1) {
			break;
		}
	}
	for (int i = 0; i < size; i++) {
		if (((arr[i] >> pos) & 1) == 1) {
			*p1 ^= arr[i];
		}
		else {
			*p2 ^= arr[i];
		}

	}
}
int main() {
	int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
	size_t size = sizeof(arr) / sizeof(arr[0]);
	int dog1 = 0;
	int dog2 = 0;
	search_signal_dog2(arr, size, &dog1, &dog2);
	printf("%d %d\n", dog1, dog2);
	return 0;
}

summary :

         Violence law is relatively mindless , But the bit operation algorithm needs to master the knowledge of XOR . That's what I'm bringing to you today leetcode Algorithm problem , If you think my content is helpful to you, remember to like it and pay attention to your collection ! I wish the handsome boys and girls in Sanlian everything they want .