题目地址
https://www.nowcoder.com/test/8537237/summary
1. 用户喜好
题目描述
为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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 2 3 3 5 3 1 2 1 2 4 5 3 5 3
输出例子1: 1 0 2
例子说明1: 样例解释: 有5个用户，喜好值为分别为1、2、3、3、5， 第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1 第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0 第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2
思路
由于查询的是连续的区间,因此我的第一想法其实是前缀和的技巧。但是由于数据不是一维的， 每个人的喜好种类有很多，因此空间复杂度是 $O(NKM)$，其 N 为用户数， KM 为喜好值 k 的种类数。 k 没有给取值范围， 从测试用例来看，应该是和 N 同阶，大概就是 $N^2$，也就是 300000 300000 = 9 * 10^10 。这个空间复杂度肯定不行。
前缀和是一个比较通用的解决这种问题的思路。 我们不使用前缀和加速的话， 简单的思路就是暴力枚举。 由于题目要求 标号为l<=i<=r的用户中对这类文章喜好值为k的用户的个数 。
-
一种思路是将喜好为 k 的人存到一个数组， 每次询问的时候遍历整个数组，时间复杂度为线性。我们可以将其存为有序的，这样可以二分，时间复杂度为对数。
-
一种思路是将每个用户的喜好存到一个数组，每次询问的时候，先找出[l, r] 之间的所有用户， 再依次遍历每个数组，时间复杂度为多项式。如果喜好按照顺序， 也可以降低复杂度到对数。不过如果 r - l 很大 ，复杂度依然很高。
很明显第一种思路代码简单， 性能也更好，我们就用第一种。
算法:
- like_mapper 记录喜好为 k 的人有哪些，其中 key 为 喜好值， value 为 userList
- 根据 k 找到 userList
- 遍历 userList 将符合条件的用户计数即可。 符合条件指的是 编号在 [l, r]
代码（Python）
from collections import defaultdict
n = int(input())
likes = list(map(int, input().strip().split()))
rounds = int(input())
like_mapper = defaultdict(lambda: [])
for i in range(n):
like_mapper[likes[i]].append(i)
while rounds > 0:
rounds -= 1
l, r, k = map(int, input().strip().split())
l -= 1 # zero base
r -= 1 # zero base
if k not in like_mapper:
print(0)
continue
cnt = 0
for like_k in like_mapper[k]:
if l <= like_k <= r: cnt += 1
if like_k > r: break
print(cnt)
复杂度分析
- 时间复杂度：$O(rounds * KV)$，其中 KV 为 like_mapper 中值的平均长度。
- 空间复杂度：$O(KV)$，其中 KV 为 like_mapper 中值的平均长度。
2. 手串
题目描述
作为一个手串艺人，有金主向你订购了一条包含n个杂色串珠的手串——每个串珠要么无色，要么涂了若干种颜色。为了使手串的色彩看起来不那么单调，金主要求，手串上的任意一种颜色（不包含无色），在任意连续的m个串珠里至多出现一次（注意这里手串是一个环形）。手串上的颜色一共有c种。现在按顺时针序告诉你n个串珠的手串上，每个串珠用所包含的颜色分别有哪些。请你判断该手串上有多少种颜色不符合要求。即询问有多少种颜色在任意连续m个串珠中出现了至少两次。
输入描述: 第一行输入n，m，c三个数，用空格隔开。(1 <= n <= 10000, 1 <= m <= 1000, 1 <= c <= 50) 接下来n行每行的第一个数num_i(0 <= num_i <= c)表示第i颗珠子有多少种颜色。接下来依次读入num_i个数字，每个数字x表示第i颗柱子上包含第x种颜色(1 <= x <= c)
输出描述: 一个非负整数，表示该手链上有多少种颜色不符需求。
输入例子1: 5 2 3 3 1 2 3 0 2 2 3 1 2 1 3
输出例子1: 2
例子说明1: 第一种颜色出现在第1颗串珠，与规则无冲突。 第二种颜色分别出现在第 1，3，4颗串珠，第3颗与第4颗串珠相邻，所以不合要求。 第三种颜色分别出现在第1，3，5颗串珠，第5颗串珠的下一个是第1颗，所以不合要求。 总计有2种颜色的分布是有问题的。 这里第2颗串珠是透明的。
思路
这道题我是看了半天才搞懂题目。
题竟然还有错别字。
第i颗柱子应该是第i颗珠子。
其实这道题已经给了你提示了，并且这道题和上面的题挺像的。
题目要求是：
- 第一种颜色出现在...
- 第二种颜色分别出现在....所以...
- 第三种颜色分别出现在...所以...
因此我们的算法很简单，就是设计一个数据结构和算法能够很快地根据颜色得到该颜色出现的珠子的位置。用一个字典就好了。
算法:
- color_mapper 每一种颜色出现在珠上的位置，其中 key 为 颜色， value 为珠子 set
之所以用 set 是为了去重
- 遍历所有的颜色，取出他们的珠子，并排序
- 如果相邻珠子距离小于 m 则计数 + 1
代码（Python）
from collections import defaultdict
n, m, c = list(map(int, input().strip().split()))
color_mapper = defaultdict(lambda: set())
ans = 0
i = 0
while i < n:
i += 1
for color in input().strip().split()[1:]:
color_mapper[color].add(i)
for color in color_mapper:
if color == '0': continue
balls = sorted(color_mapper[color])
for j in range(1, len(balls)):
if balls[j] - balls[j - 1] < m or balls[j - 1] - balls[j] < m - n:
ans += 1
break
print(ans)复杂度分析
- 时间复杂度：$O(n * KVlogKV)$，其中 KV 为 color_mapper 中值的平均长度。
- 空间复杂度：$O(KV)$，其中 KV 为 color_mapper 中值的平均长度。
更多题解可以访问我的LeetCode题解仓库：https://github.com/azl397985856/leetcode 。 目前已经35K star啦。
关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。
