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

在线编程介绍

阿里云开发者社区在线编程产品，针对广大开发者学习、实践、面试、应聘、考试认证等打造的免费在线刷题神器。题库来自笔试模拟题、算法大赛模拟题等，界面整洁明了，操作简单，为用户营造专心答题的学习环境。点击链接开始体验：

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)

看完之后是不是有了想法了呢，快来练练手吧>>