专栏简介 :刷题笔记

题目来源:leetcode,牛客,剑指offer

创作目标:多维度归纳总结,刷题时遇到的拓展性强,重复高的题目与解题思维.

希望在提升自己的同时,帮助他人,,与大家一起共同进步,互相成长.

学历代表过去,能力代表现在,学习能力代表未来!

        前言:今天给大家带来的这道力扣原题,有很多种解法 ,不同解法对应的难度不同,所以今天带给大家两个解法,暴力和位运算.一简单,一中等.

         一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。

一.暴力解法:

        举一个极端亿点点的案例:2 2 4 6 5 8 4 6,首先对其冒泡排序:2 2 4 4 5 6 6 8,接着将排序好的数组一一比较即可.看似简单的逻辑时间复杂度要O(N^2).可以说非常的耗时了.不了解时间复杂度的可以看我之前的博客有时间复杂度最0基础的讲解.CSDN

#include<string.h>
#include<errno.h>
void search_signal_dog1(int arr[],int size) {	
	for (int i = 0; i < size-1; i++) {//冒泡排序之后: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;) {//排序之后直接比较就行
		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);

 二.位运算的方法:

        首先我们将[1,2,3,4,5,1,2,3,4,6]存入一个数组中.其中5和6是单独的数字.如果我们对整个数组异或,那么相同的元素异或为0,不同的元素异或后会变成另一个数,本例中异为:ret=5^6=3.然后由异或的特性可知:两个数异或后不同位为1,相同位为0,所以我们找到ret中二进制的第pos位是1.记录下pos位后我们遍历一下数组,数组中移动pos位按位与1==1的为一组,不等于1的为一组.分成两组之后,对各自组内的元素异或即可得到答案.

void search_signal_dog2(int arr[], int size, int* p1, int* p2) {
	//1.异或
	int ret = 0;
	for (int i = 0; i < size; i++) {
		ret ^= arr[i];//5^6
	}
	int pos = 0;
	//2.计算ret的二进制位中第几位是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;
}

总结:

        暴力法较为无脑,但位运算法需要熟练掌握异或的知识.以上就是今天为大家带来的leetcode算法题,如果觉得我的内容对你有帮助记得点赞关注收藏哦!祝三连的帅哥美女心想事成.