← 返回目录

2.2 搜索

第 41 / 74 卷日期：

2.2搜索

算法笔试模拟题精解之“2 的幂次方数”

贡献者 | 洪浩原

简介：对于本题，因为要从数组中删除数字。删除分为两步，一是定位（查找），

二是删除（将出现次数减 1）。

题目描述

等级：中等

知识点：数学、枚举

查看题目：2 的幂次方数

Tom 是一个十分喜欢数学的人，尤其喜欢 2 的幂次方的数字。现有 n

（1<=n<=150000）个数字，对于其中的每一个数字 ai(1<=i 输入数字个数 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)

看完之后是不是有了答题思路了呢，快来练练手吧：2 的幂次方数

全站分卷索引 · 74 卷
  1. 1一、算法思想
  2. 2算法笔试模拟题精解之“打怪兽”
  3. 31.2 贪心
  4. 4算法笔试模拟题精解之“最强的团队”
  5. 5算法笔试模拟题精解之“Tom 爱吃巧克力”
  6. 6算法笔试模拟题精解之“吃奶酪”
  7. 7算法笔试模拟题精解之“一的个数”
  8. 8算法笔试模拟题精解之“Bob 的花束”
  9. 9算法笔试模拟题精解之“钱庄”
  10. 10算法笔试模拟题精解之“移动射击”
  11. 11算法笔试模拟题精解之“相似数组”
  12. 12算法笔试模拟题精解之“过吊桥”
  13. 13算法笔试模拟题精解之“完美排列”
  14. 14算法笔试模拟题精解之“采摘圣诞果”
  15. 15算法比赛模拟题精解之“Tairitsu and Dynamic Objects”
  16. 16算法笔试模拟题精解之“Codancer 的炸弹引爆”
  17. 17算法笔试模拟题精解之“学习小组”
  18. 18算法笔试模拟题精解之“恢复字符串”
  19. 191.3 DP/ 动态规划
  20. 20算法笔试模拟题精解之“寻找等比数列”
  21. 21算法笔试模拟题精解之“字符配对”
  22. 22算法笔试模拟题精解之“数组染色”
  23. 23算法笔试模拟题精解之“连绵的群山”
  24. 24算法笔试模拟题精解之“难住Tom 的问题”
  25. 25算法笔试模拟题精解之“变化的字符”
  26. 26算法笔试模拟题精解之“跳房子”
  27. 27算法笔试模拟题精解之“寒假活动”
  28. 28算法笔试模拟题精解之“最短路”
  29. 29算法笔试模拟题精解之“codancer 上楼”
  30. 30算法笔试模拟题精解之“木棒拼接”
  31. 31算法笔试模拟题精解之“Codancer 的数组封印”
  32. 32算法笔试模拟题精解之“Jerry 的异或运算”
  33. 33算法笔试模拟题精解之“小明的数学作业”
  34. 34算法笔试模拟题精解之“奇偶数列”
  35. 351.4 剪枝
  36. 361.5 尺取法
  37. 37算法笔试模拟题精解之“调整数组”
  38. 38算法笔试模拟题精解之“最优分组”
  39. 39算法笔试模拟题精解之“破译密码”
  40. 40二、数据结构
  41. 412.2 搜索
  42. 42算法笔试模拟题精解之“能量半径”
  43. 43算法笔试模拟题精解之“苹果收获程序”
  44. 44算法笔试模拟题精解之“恐怖的辐射”
  45. 45算法笔试模拟题精解之“树的拆分”
  46. 46算法笔试模拟题精解之“Password”
  47. 47算法笔试模拟题精解之“神奇数字在哪里”
  48. 48算法笔试模拟题精解之“神奇的棋子”
  49. 492.3 树
  50. 50算法笔试模拟题精解之“Codancer 的旅行”
  51. 51算法笔试模拟题精解之“Codancer 的求和”
  52. 52算法笔试模拟题精解之“找出二叉搜索树的第2 大的数”
  53. 532.4 线型
  54. 54算法笔试模拟题精解之“最活跃的数”
  55. 55算法笔试模拟题精解之“非递减序列”
  56. 56算法笔试模拟题精解之“Tom 跳方格”
  57. 57算法笔试模拟题精解之“复杂的字符串”
  58. 58算法笔试模拟题精解之“神秘消失”
  59. 59三、计算
  60. 60算法笔试模拟题精解之“简单题？
  61. 61算法笔试模拟题精解之“朋友一生一起走”
  62. 62算法笔试模拟题精解之“正三角塔”
  63. 63算法笔试模拟题精解之“组队难题”
  64. 64算法笔试模拟题精解之“2n 合体”
  65. 65算法笔试模拟题精解之“平行线”
  66. 66算法笔试模拟题精解之“叠叠高”
  67. 67算法笔试模拟题精解之“公平”
  68. 68算法笔试模拟题精解之“Tom 的手工课”
  69. 69算法笔试模拟题精解之“填数问题”
  70. 70算法笔试模拟题精解之“Jerry 的考验”
  71. 71算法笔试模拟题精解之“超车”
  72. 72算法笔试模拟题精解之“坏掉的时钟”
  73. 73算法笔试模拟题精解之“期末考试”
  74. 74算法笔试模拟题精解之“滑雪比赛”