剑指40-数组中只出现一次的数字
数组 数字 出现 一次 40
2023-06-13 09:16:12 时间
位运算、哈希表
题目描述
一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
解法1
遍历数组,用map保存出现的次数,再找到次数为1的数
class Solution {
public:
void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
map<int, int> map;
for (int i = 0; i < data.size(); i++)
map[data[i]]++;
vector<int>v;
for (int i = 0; i < data.size(); i++)
if (map[data[i]] == 1)
v.push_back(data[i]);
*num1 = v[0]; *num2 = v[1];
}
};
解法2
- 如果两个数字相同,那么他们异或的结果为0 所以将所有数字异或,结果就是两个只出现一次的数字异或的结果
- 那么如何分离这两个数字呢 异或结果为1时,两个数字里对应的位肯定为1和0,所以找到异或结果为1的位置ret &= (-ret); 假如ret = 1110 , -ret = 0010 , 所以 i = 0010
- 再和每个数字做与操作,如果为1,则异或到num1,不为1则异或到num2
总结下流程为:所有数组异或–>和反码与得到1的位置–>和每个数字与判断–>对应再异或
class Solution2 {
public:
void FindNumsAppearOnce(vector<int> data, int* num1, int *num2) {
int ret = 0;
for (const int k : data) ret ^= k;
ret &= (-ret); //找ret二进制中为1的位置
*num1 = 0, *num2 = 0;
for (const int k : data) { //再分别异或一次
if (k & ret) *num1 ^= k;
else *num2 ^= k;
}
}
};
相关文章
- js对象数组添加元素
- 剑指 Offer 56 – I. 数组中数字出现的次数
- 剑指 Offer 03. 数组中重复的数字(原地算法)「建议收藏」
- C语言通过指针引用数组【C语言学习笔记】
- c-计蒜客 排序好的数组删除重复数字
- 【Linux C语言编程】使用hexdump打印字节数组
- 盘盘项目中你常用到的数组API
- 剑指37-数字在排序数组中出现的次数
- 2023-02-16:两种颜色的球,蓝色和红色,都按1~n编号,共计2n个, 为方便放在一个数组中,红球编号取负,篮球不变,并打乱顺序, 要求同一种颜色的球按编
- 【C 语言】数组 ( 多维数组做函数形参退化为指针过程 | int array[2][3] -> int array[][3] -> int (*array)[3] )
- 【算法】二分法 ③ ( 山脉数组的峰顶索引 | 枚举法 | 二分法 )
- Java的字节(byte)数组与Python3中的字节类型负值问题
- 每日一题:数组中数字出现的次数2
- postgresql 数据库基础 之 如何实现将数组变为行
- mongodb 数据类型(null/字符串/数字/日期/内嵌文档/数组等)
- go语言之切片即动态数组详解编程语言
- PHP array_values():获取数组中所有元素的值
- js中将具有数字属性名的对象转换为数组
- perl数组的多数字下标示例代码
- javascript操作数组详解