Given an array of integers, every element appears three timesexcept for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement itwithout using extra memory?

HideTags

 Bit Manipulation

#pragma once
#include<iostream>
#include<map>
using namespace std;

//法1：排序

//法2：STL容器map
int singleNumber2(int A[], int n) 
{
	map<int, int> m;
	map<int, int>::iterator it;
	for (int i = 0; i < n; i++)
	{
		it = m.find(A[i]);
		if (it == m.end())
			m[A[i]] = 1;
		else
			//m[A[i]]++;
			it->second++;
	}
	for (int i = 0; i < n; i++)
		if (m.at(A[i]) == 1)//at与find区别：at返回索引值对应的value，可能越界
			return A[i];
}

//法3：位运算。考虑全部用二进制表示，如果我们把 第 ith  个位置上所有数字的和对3取余，那么只
//会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0).  因此取余的结果就是那个 “Single Number”.

int singleNumber3(int A[], int n)
{
	//int四字节32位，每位和由一个数记录
	int count[32] = { 0 };//每个元素都置0
	int result = 0;
	for (int i = 0; i < 32; i++)//32位
	{
		for (int j = 0; j < n; j++)//n个数
			if (A[j] >> 1 & 1)//注意，操作只有一个&，判断才有俩
				count[i]++;
		result |= ((count[i] % 3) << i);//好好体会。“|”：位或
	}
	return result;
}

//法4：改进的位运算。
int singleNumber4(int A[], int n)
{
	int ones = 0, twos = 0, threes = 0;
	for (int i = 0; i < n; i++)
	{
		//注意，每次循环前，ones twos threes互不相交
		twos |= ones&A[i];//新2 = 原2不在A[i] + 原2在A[i]
		ones ^= A[i];//新1 =  原1不在A[i] + 原非1在A[i]
		//于是，新2 & 新1 = 原2在A[i]。即交集部分出现了3次，将交集部分在ones和twos中置0，ones twos就保证A[i]之后合理
		threes = ones&twos;//注意threes意义并不是指A[i]后三次的位而是，这层循环中新产生的三次位
		ones ^= threes;//ones &= ~threes;也行，但前者较快
		twos ^= threes;//twos &= ~threes;也行，但前者较快
	}
	return ones;
}

void main()
{
	int A[] = { 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5 };
	cout << singleNumber3(A, 13) << endl;
	system("pause");
}

137.Single Number II（法1排序法2STL容器map哈希法3位运算法4改进的位运算）