《剑指offer》:统计数组中各数字的次数


《剑指offer》题目:一个整型数组里除了两个数字之外,其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。我用map去统计出现的次数,但是最后返回
两个数的时候,感觉使用的方法特别笨,哪位大神有更好的返回方法不?
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]]++;
bool flag = true;
for(int i = 0; i < data.size(); i++){
if(map[data[i]] == 1)
{
if(flag){
*num1 = data[i];
flag = false;
}
else
*num2 = data[i];
}
}
}
};

#笔试题目##C/C++#
全部评论
多看题目讨论区别人分享的思路。这道题要用异或的特性。最优解是o(n)时间复杂度 o1空间复杂度。 剑指offer的题目不能只看它是否ac,关键写出算法最优解。https://github.com/ReyzalX/nowcoder 这里有我写的剑指offer的所有题目代码,以及其他公司套题代码。可供参考。
点赞 回复 分享
发布于 2018-03-17 02:09
map有额外空间。可以两两异或,得到的就是两个不同数字的异或。然后找到1那一位,就是不同的一位。然后按此位是否为1将数字分为两组,分别两两异或,得到结果
2 回复 分享
发布于 2018-03-16 20:49
异或思想,一个数与自己异或为0,一个数与0异或为自己 由于其它数字两两相同,所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位 这个标志的1,必须是:这两个数在该位一个为0,一个为1,因为是异或操作,结果为1必然在这里两个数字一个为0一个为1 这里的结果必须是会产生的,也就是说肯定存在异或结果为1,不然这两个数字就是相等的 这样可以将数组分为两组,一组在该标志位为1,一组在该标志位为0,这两个不同数字分别在这两组内 将两组内的数分别异或,得到两个结果则为这两个不同的数
点赞 回复 分享
发布于 2018-03-16 19:33
位运算
点赞 回复 分享
发布于 2018-03-16 22:06
自己可以看答案的啊,下面一堆优秀的答案。
点赞 回复 分享
发布于 2018-03-16 20:16

相关推荐

喜欢飞来飞去的雪碧在刷代码:可以试一试字节
点赞 评论 收藏
分享
04-27 08:59
常州大学 Java
牛客139242382号:《两门以上汇编语言》
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务