← 返回目录

算法笔试模拟题精解之“组队难题”

第 63 / 74 卷日期：

算法笔试模拟题精解之“组队难题”

贡献者 | 郭达彬

简介：根据题意，本题需要找出符合 a ⊕ b>max(a,b) 条件的队伍，如果使用两

重循环，两两判断学生是否符合条件，会超出时间限制。

题目描述

题目等级：容易

知识点：位运算

查看题目：组队难题

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

输入：

[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)

看完之后是不是有了想法了呢，快来练练手吧 >> 查看题目：组队难题

全站分卷索引 · 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算法笔试模拟题精解之“滑雪比赛”