[剑指offer] 40. 数组中只出现一次的数字

题目描述

一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。

---

思路： 解法一: 哈希表 class Solution { public: void FindNumsAppearOnce(vector<int> data, int *num1, int *num2) { map<int, int> mapping; for (int i = 0; i < data.size(); i++) mapping[data[i]]++; vector<int> v; for (int i = 0; i < data.size(); i++) { if (mapping[data[i]] == 1) v.push_back(data[i]); } *num1 = v[0]; *num2 = v[1]; } };

解法二：

利用异或

1、异或思想，一个数与自己异或为0，一个数与0异或为自己 2、由于其它数字两两相同，所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位 3、这个标志的1，必须是：这两个数在该位一个为0，一个为1 4、这样可以将数组分为两组，一组在该标志位为1，一组在该标志位为0，这两个不同数字分别在这两组内 5、将两组内的数分别异或，得到两个结果则为这两个不同的数 class Solution { public: void FindNumsAppearOnce(vector<int> data, int *num1, int *num2) { int tempbit = 0; for (auto c : data) tempbit ^= c; int sign = 0; //记录两个数不同的那一位 for (; sign < data.size(); sign++) { if ((tempbit & (1 << sign)) != 0) break; } *num1 = 0; *num2 = 0; for (auto c : data) { if ((c & (1 << sign)) == 0) *num1 ^= c; else *num2 ^= c; } } };

 

 

转载于:https://www.cnblogs.com/ruoh3kou/p/10153048.html