当前位置:网站首页>找两个单身狗
找两个单身狗
2022-08-09 05:13:00 【潜水少年请求出战】
题目:
一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
我先说怎么找一个独立的数:例子:123 4 123找这里面的的4我们可以异或一下。
异或(^):相同的数异或为0;相异的数异或为1(二进制位)
101 (5) 111
110 (6) 111
011 (3)异或后 0
我们利用异或的特点找到1234123中的4就是那条单身狗。
现在要找到俩条单身狗思路:找出一个只出现过一次的数字的问题处理方法就是找一个数字把里面所有的数字都异或一遍,利用异或两次等于没异或的特点来处理。那么如果有两个数字都只出现了一次,那么如此得到的应该是两个数异或的结果。首先这个结果肯定不是0(要不然就全都配对了),所以里面一定至少一位是一。找出值为1的一位,以这一位的值将结果分为两组。例如1 2 3 4 1 2,异或完的结果应该是3^4得到的111,那么随便找一位就行了。例如找最低位,那么这一位是1的有1 3 1,是0的有2 4 2,由于是利用异或结果为1的某一位分的组,所以两个待查询数字一定分别在两组中。所以再找两个变量,分别异或两组数,即可找到这两个数。
下面代码:
//找单身狗 //思路:利用 ^ 这个符合来找(相同为0); #include<stdio.h> void f_t_dog(int* arr, int sz) { int fdog1 = 0; int fdog2 = 0; //先异或一下。 int ret = 0; int i = 0; int j = 0; for (i = 0; i < sz; i++) { ret ^= arr[i]; } //找到异或后的ret中二进制位的一个1。 for (i = 0; i < 32; i++) { if (((ret >> i) & 1) == 1) break; } //分组 for (j = 0; j < sz; j++) { if (((arr[j] >> i) & 1) == 1) fdog1 ^= arr[j]; } //找第二个单身狗。 fdog2 = ret ^ fdog1; printf("%d %d\n", fdog1, fdog2); } int main() { int arr[] = { 1,2,3,4,6,1,2,3,4,9 }; int sz =sizeof(arr)/sizeof(arr[0]); f_t_dog(arr, sz); return 0; }
边栏推荐
猜你喜欢
随机推荐
什么是通用微处理器、单片机、DSP芯片、嵌入式系统?
数据库事务&锁机制
降压模块的使用
神经网络预测应力应变-单轴实验
C进阶-C语言文件操作
想要精准营销,从学习搭建一套对的标签体系开始丨DTVision分析洞察篇
STM32系列单片机使用心得
华为鲲鹏生态培训试题
Parameters in dynamic libraries cannot be modified through macro definitions or global variables in header files
C Advanced - Program Compilation (Preprocessing) + Linking
Quantitative Genetics Heritability Calculation 1: Parent-Child Regression Method
不能提取结果集,SQL [n / a]; org.hibernate.exception.SQLGrammarExcept是嵌套的异常
Storage System Architecture Evolution
保存Simulink仿真模型为图片或者PDF的方法
算法---优美的排列(Kotlin)
mysql查看表的创建时间
绕过反调试fuck-debugger
软件测试工程师简历要怎么写,才能让HR看到
数字化时代,企业为什么需要商业智能BI
MySQL LIMIT + order by limit n,m 和 limit n的小坑