题解 | #数组中只出现一次的两个数字#
数组中只出现一次的两个数字
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>
本题的方法二使用的是位运算,没有看懂。