算法筆試模拟題精解之“組隊難題”

線上程式設計介紹

阿裡雲開發者社群線上程式設計産品，針對廣大開發者學習、實踐、面試、應聘、考試認證等打造的免費線上刷題神器。題庫來自筆試模拟題、算法大賽模拟題等，界面整潔明了，操作簡單，為使用者營造專心答題的學習環境。點選連結開始體驗：

https://developer.aliyun.com/coding

本文為大家介紹其中的 第81題：組隊難題 的題目解析，具體如下：

題目描述

題目等級：容易

知識點：位運算

檢視題目：組隊難題

H大學迎來了一年一度的羽毛球雙打比賽，小夥伴們都很積極地報了名。

但是為了達到1⊕1>1（注：a⊕b>max(a,b)）的效果，學校給每位同學進行了實力認證，每位同學都獲得了一個能力值。在組隊的時候，組成隊伍的兩位同學的能力值a,b必須滿足條件：a⊕b>max(a,b)。

校長想要統計一共可以組成多少不同的隊伍，請你幫助校長計算出來。

輸入學生數n(2<=n<=10^5)和n個正整數ai(1<=ai<=10^9)，表示每位同學的能力值。

輸出一個整數，表示一共可以組成的隊伍總數

示例1

輸入：

5

[1,2,3,4,5]

輸出：

6

注意

1、如果兩個隊伍至少有一個隊員不相同，這兩個隊伍就是不同的。

2、每位同學可以同時出現在不同的隊伍中。

解題思路

根據題意，本題需要找出符合 a⊕b>max(a,b) 條件的隊伍，如果使用兩重循環，兩兩判斷學生是否符合條件，會超出時間限制。

本題的限制條件 a⊕b>max(a,b) 中，假設 a < b，b = 1001（該數字為二進制形式），從右往左數，可以發現數字 b 的第二位和第三位為 0，若 a 想要滿足限制條件和 b 組隊，數字 a 的最高位必須為數字 b 值為 0的對應的位，即第二位和第三位，若a等于100或10，均可以滿足條件和b組隊。

了解了上一步之後，可以統計每個數字中 0 出現位置，比如第三位是0的數字在數組中有多少。用HashMap進行存儲，以 0 的位置為 key，對應位置為0的數字的數量為 value。

統計完所有 0 出現的次數後，周遊數組，計算每個數字的二進制的位數，在 HashMap 中取出對應的value。在周遊數組的過程中，對所有取出的value值求和即可得到可以組成的隊伍總數。

時間複雜度：O(n)

空間複雜度：O(n)

看完之後是不是有了想法了呢，快來練練手吧>>