#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>using namespace std;/*問題:Given an array of integers, every element appears three times except for one, which appears exactly once. Find that single one.Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?分析:數組中每個元素出現了3次，只有一個元素出現了1次，找到這個元素。必須在線性時間找到。盡量不要使用額外的空間。每個元素出現了3次，如果用異或所有元素不就相當于每個元素都參與了異或嗎？這個好像也是劍指offer的題目。好像是從位來入手的。舉個例子:假設有元素1,1,1,2,2,2,3,3,3,4如果全部異或的結果sum=1^2^3^4=00010010001101000100如果我拷貝這個數組A，對數組A中所有元素異或兩次，那么每個元素都出現了6次另外一個元素肯定也出現了偶數次，那么整個結果為0。先簡化題目：如果所有元素都出現1次，只有一個元素出現了兩次，那么如何找到這個元素。直接桶排序不就行了嗎，但是桶排序需要知道元素的最小和最大值范圍。此題明顯沒有給出這樣的條件可以用哈希map或者map。當然這是使用了額外的空間。如果不能使用額外的空間。劍指offer中指出如果丟失了兩個不同的數(各自出現一次，其余出現兩次)，可以比較所有元素的異或和中的對應bit位，然后不斷按照bit位分組。編程之美如果丟失了兩個兩個數(各自出現一次，其余出現兩次)，可以用構造二元一次方程組來做。此題輸入:101 1 1 2 2 2 3 3 3 4輸出:4關鍵:1 leecode的解法:https://leetcode.com/PRoblems/single-number-ii/?tab=Solutions想不到。對0~31位上，統計每個數在每一位上出現次數，如果出現的總次數sum % 3 != 0說明這一位肯定是只出現了一次的那一位，把所有位異或連接，即可。獲取每個數第i位用: 掩碼mask = 1 << 1，然后 mask & nums.at(i) 即得到2 關鍵就是通過位操作來解決計數問題*/class Solution {public:    int singleNumber(vector<int>& nums) {		if(nums.empty())		{			return 0;		}        unordered_map<int , int> numToTimes;		int size = nums.size();		int mask;		int sum;		int result = 0;		for(int i = 0 ; i < 32 ; i++)		{			mask = 1 << i;			sum = 0;			for(int j = 0 ; j < size ; j++)			{				//這里相與結果是第i位為1或者全0				if((nums.at(j) & mask) != 0)				{					sum++;				}			}			if(sum % 3 != 0)			{				result |= mask;			}		}		return result;    }};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}void process(){	 vector<int> nums;	 int value;	 int num;	 Solution solution;	 vector<int> result;	 while(cin >> num )	 {		 nums.clear();		 for(int i = 0 ; i < num ; i++)		 {			 cin >> value;			 nums.push_back(value);		 }		 num = solution.singleNumber(nums);		 cout << num << endl;	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}