筆試算法模拟題精解之“2的幂次方數”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“40題.2的幂次方數”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：數學、枚舉

檢視題目：2的幂次方數

Tom是一個十分喜歡數學的人，尤其喜歡2的幂次方的數字。現有 n（1<=n<=150000）個數字，對于其中的每一個數字 ai(

1<=i<n, 1<=ai<=1000000000

)，Tom希望找到除了它自己以外的一個數 aj( i != j )，使得 ai+aj 是一個2的幂次方數，如果找不到就将這個數删除，問最終需要删除多少個數字?

輸入數字個數n和n個數字；

輸出一個數字，表示最終需要删除的數字的個數。

示例1

輸入：

3

[1,2,3]

輸出：

1

解題方法 ：位運算

對于本題，因為要從數組中删除數字。删除分為兩步，一是定位（查找），二是删除（将出現次數減1）。是以首先需要考慮的難題是，如何快速定位要查找的數字，并記錄下數字出現的次數？for循環的線性查找，遞歸的二分查找（對有序數組），建立哈希表，都是可選的方式。既然追求最佳解法，你不妨先試試将題目提供的資料結構轉為哈希表？

之後的第二個難點，就是如何得出“與某個數相加為2的幂次方數”的數字了。我們知道，用二進制表示時，一個2的幂次方的正整數，譬如2，4，8，16...，隻有最高位為1，其餘位都是0，譬如b1，b10，b100，b1000...是以，對每個數字，隻要用位元算找到它的最高位1的位置，就可以确定比它大的2的幂次方數中最小的數字了。

本題最後的陷阱，在于正确了解 “與這個數相加為2的幂次方數”的條件。舉個例子來說，對于數字1，它不僅與1相加為2的幂次方數，與3，7，15...相加後，結果都是2的幂次方數。很多同學想到位運算的時候，可能忽略了這個條件，而隻考慮了比數字大的2的幂次方數中最小的數字

時間複雜度：O(31n)（考慮到本題Integer正整數所占的二進制位數

空間複雜度：O(n)

看完之後是不是有了答題思路了呢，快來練練手吧：

第40題.2的幂次方數

上一篇： 筆試算法模拟題精解之“Alice的01串”的三種解法