筆試題(交集)

才智咖 人氣:1.27W

  筆試題:兩個整數集合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的值。

TAGS:筆試