今日头条2018校招后端方向(第二批)笔试的一道算法题。
题目
为了不断优化推荐效果,今日头条每天要存储和处理海量数据。
假设有这样一种场景:我们对用户按照它们的注册时间先后来标号,对于一类文章,每个用户都有不同的喜好值,
我们会想知道某一段时间内注册的用户(标号相连的一批用户)中,有多少用户对这类文章喜好值为k。
因为一些特殊的原因,不会出现一个查询的用户区间完全覆盖另一个查询的用户区间(不存在 L1<=L2<=R2<=R1)。
输入描述
第1行为n代表用户的个数。
第2行为n个整数,第i个代表用户标号为i的用户对某类文章的喜好度。
第3行为一个正整数 q 代表查询的组数 。
第4行到第(3+q)行,每行包含3个整数 l,r,k 代表一组查询,即标号为 l<=i<=r 的用户中对这类文章喜好值为k的用户的个数。
数据范围n <= 300000,q<=300000,k是整型。
输出描述
输出:一共q行,每行一个整数代表喜好值为k的用户的个数
示例
输入
1 | 5 |
输出
1 | 1 |
样例解释
样例解释: 有5个用户,喜好值为分别为1、2、3、3、5,
第一组:求 1~2 范围内,喜好值为1的用户总数是多少,结果是 1。
第一组:求 2~4 范围内,喜好值为5的用户总数是多少,结果是 0。
第一组:求 3~5 范围内,喜好值为3的用户总数是多少,结果是 2。
牛客网题目链接
分析
直接遍历有可能会超时。
所以把相同值的用户数据的索引存到一个线性表中,同时根据这个值把所有的线性表都保存在一个 map 中。
然后根据查询范围的索引在用户数据索引中二分查找,然后索引之间相减即可。
解答1[Java]:
1 | import java.io.File; |
代码解释
关于 lowerBound 和 upperBound
首先,lowerBound 和 upperBound 都是 list 中的索引。所以 list 中 [lowerBound, upperBound) 这个区间的用户数据,就从属于总数据的 [l, r]
这个区间。
lowerBound 和 upperBound 相当于是左闭右开的,即 [lowerBound, upperBound),所以直接用 upperBound - lowerBound
赋值给 hitNum
。
computeIfAbsent()
Java 8 中 Map 接口引入的新方法。
当第一个参数看作 key,当 key 不在 map 中时,调用第二个参数,也就是一个方法进行 compute,把第二个参数作为 value,然后把这对 \add()
方法为 list 添加值。
下标
我在读入数据的时候直接把下标设为从 1 开始,这样后边读入 l 和 r 的时候就不需要进行减 1 了。
测试时候用的 main 方法
解答中的 main()
方法是提交时候用的,测试时候使用的是下边这个。
1 | public static void main(String[] args) { |
再分析
如果查询区间,也就是 r - l
普遍很小,那么直接遍历是比较好的方法。
如果喜好值有取值范围的话,可以进一步优化。
假如喜好值取值范围是 0~10,数据总量为300000时,平均每个喜好值的重复数量为 30000,如果用二分查找,平均查找15次,上下界要查找两次,平均查找30次,如果 r - l
的值小于30,可以选择直接遍历原数据 l~r。
空间复杂度的考虑,
一种算法是存进二位数组,而后对二位数组进行排序。但是最初的顺序就乱了。失去了遍历原数据的可能性。
第二种就是直接存在map中的list中,不过也直接失去了遍历原数据的可能性。
补充
C++ 的 STL 中有现成的 lower_bound
、upper_bound
、equal_range
等函数,位于 <algorithm>
头文件中,如果熟悉 C++,直接用 C++ 写还是很方便的。可以参考这篇文章看看 C++ STL 中是如何实现的。
看牛客上有人说还可以考虑使用莫队算法,可以参考莫队算法学习笔记了解一下莫队算法。
upperBound()
和 lowerBound()
使用的是二分查找,要仔细检查,以防写错。可以参考: