当前位置:网站首页>找两个单身狗
找两个单身狗
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; }
边栏推荐
- Harmony OS ets ArkUI 】 【 】 development create a view and building layout
- 浅谈单片机Boot的几种自刷新方式
- C Advanced-C Language File Operation
- 通讯录(动态版)(C语言)(VS)
- How to trim svg and compress
- Faced with risk control, what should Amazon do when evaluating self-supporting accounts?
- Anonymous shared memory ashmem
- p67 mixin 混入/混合:两个组件共享一个配置
- 【基于富瀚6630使用/dev/fb0显示设备和TDE模块渲染bmp图像】
- Docker部署MySQL
猜你喜欢
硅光电池采集用于植物叶片农残检测
微服务架构基础 微服务相关概念及基础知识 贺兰的微博
22-08-08 西安 尚医通(04)MongoDB命令、MongoTemplate、MongoRepository
软件测试的方法详细介绍
Openresty执行lua脚本
Why do enterprises need business intelligence BI in the digital age
剑指Offer - 链表翻转及其变体题目总结
PWM输出模块PCA9685
滑动窗口篇
Quantitative Genetics Heritability Calculation 1: Parent-Child Regression Method
随机推荐
滑动窗口篇
Pycharm Debug调试使用+代码调试理解
【ManageEngine】网络性能监控工具
JDBC_PreparedStatement预编译对象
图解LeetCode——761. 特殊的二进制序列(难度:困难)
详谈归并排序时间复杂度过程推导----软考
硅光电池采集用于植物叶片农残检测
区别如下概念:助记符、汇编语言、汇编语言程序和汇编程序。
地理空间分析库turf.js的学习
STM32Cube学习笔记(delay)
Zuul---路由功能
Anonymous shared memory ashmem
Shell 文本三剑客 (grep、sed、awk)
明明加了唯一索引,为什么还是产生重复数据?
剑指Offer-二叉树路径问题总结
【Harmony OS】【FAQ】Hongmeng Questions Collection 1
mysql content does not exist error
74HC595 的使用
Eureka-Server------单节和集群的搭建
p67 mixin 混入/混合:两个组件共享一个配置