笔试题交集

笔试题（交集）

笔试题：两个整数集合A和B，求其交集

　　两个整数集合A和B，求其交集。

　　分析：

　　1. 读取整数集合A中的整数，将读到的整数插入到map中，并将对应的值设为1。

　　2. 读取整数集合B中的整数，如果该整数在map中并且值为1，则将此数加入到交集当中，并将在map中的对应值改为2。

　通过更改map中的.值，避免了将同样的值输出两次。

　　笔试题：找出1到10w中没有出现的两个数字

　　分析：

　　有1到10w这10w个数，去除2个并打乱次序，如何找出那两个数?

　　申请10w个bit的空间，每个bit代表一个数字是否出现过。

　　开始时将这10w个bit都初始化为0，表示所有数字都没有出现过。

　　然后依次读入已经打乱循序的数字，并将对应的bit设为1。

　　当处理完所有数字后，根据为0的bit得出没有出现的数字。

　　首先计算1到10w的和，平方和。

　　然后计算给定数字的和，平方和。

　　两次的到的数字相减，可以得到这两个数字的和，平方和。

　　所以我们有

　　x + y = n

　　x^2 + y^2 = m

　　解方程可以得到x和y的值。