题解 | #数组中只出现一次的两个数字#

数组中只出现一次的两个数字

http://www.nowcoder.com/practice/389fc1c3d3be4479a154f63f495abff8

题目:
描述
一个整型数组里除了两个数字只出现一次,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
示例1
输入:[1,4,1,6]
返回值:[4,6]
说明:返回的结果中较小的数排在前面

前面剑指offer关于数组重复的问题已经有了几道,思路很像,但是自己想到的并不多,还是要多多进行复习。
方法一:
hash方法:通过hash表的方法建立对应的key-value,再对hash表进行遍历,找到对应的出现一次的array[i]。因为对数据的排序有要求,因此使用了swap()进行交换。
vector<int> FindNumsAppearOnce(vector<int>& array) {
// write code here
vector<int>B;//新定义的数组,可以不定义大小
unordered_map<int,int>map;
int j = 0;
for(int i = 0; i < array.size(); i++)
{
map[array[i]]++;
}
for(int i = 0; i < array.size();i++)
{
if(map[array[i]] == 1)
{
B.push_back(array[i]); //尾部插入元素array[i]
}
}
if(B[0] > B[1])
{
swap(B[0],B[1]);
}
return B;
}
时间复杂度:O(n)
空间复杂度:O(n)</int></int></int>

本题的方法二使用的是位运算,没有看懂。

全部评论

相关推荐

11-26 00:10
门头沟学院 Java
chenxinxu:现在招聘的都学精了,你光学点数据库和中间件做个应用型项目人家看不上,你得有点可以“吹水”的高谈阔论的“高大上”的玩意,比如写点什么“基于分布式 Raft 共识性算法的XXX”balabala 的,然后做了什么详尽的 benchmark 怎么优化的吞吐率性能之类的,看起来就是科研论文研究领域。现在人不都这样吗,他知道的知识都是白菜,他不知道的领域都是高端,找点让大部分人看起来高端的玩意写
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务