首页 > 试题广场 >

用户喜好

[编程题]用户喜好

热度指数：8614 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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

输入

输出

1
0
2

说明

样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2

算法知识视频讲解

Python

阿耀哥

读题挺费劲的，语文没学好。

一开始使用的暴搜，代码很简单，但是通不过啊。猜到，估计测试输入的数据可能会很大。

参考楼上牛客447189284号的思路写的。用的dict。用dict，提前把用户的数据分好类。直接从分类里面检索，速度会省很多。

再次感谢牛客447189284号

N=int(input())
s=list(map(int,input().split()))
user_dict={}    #建立空的dict
for x in range(N):
    if user_dict.__contains__(s[x]):   #如果包含该key，则直接向value追加数据。value里面是list
        user_dict[s[x]].append(x+1)
    else:
        user_dict[s[x]]=[x+1]       #如果不包含该key，添加。

M=int(input())
for x in range(M):
    [l,r,k]=list(map(int,input().split()))   #边循环，边处理
    result = 0
    if user_dict.__contains__(k):  
        for y in user_dict[k]:
            if l<=y<=r:
                result+=1
    print(result)

编辑于 2020-02-12 16:41:47 回复(0)

Python

牛客447189284号

n = int(input())   #这道题用暴搜肯定超时，但是用Python的字典会非常简单

user_array = list(map(int,input().strip().split()))

user_dict = dict()            #创建一个字典
for i in range(len(user_array)):   #对应的键值是用户喜爱程度，value值是一个列表，对应相应的用户id
   if user_dict.__contains__(user_array[i]):
      user_array_list_i = list(user_dict[user_array[i]])
      user_array_list_i.append(i+1)
      user_dict[user_array[i]] = user_array_list_i
   else:
      user_array_list_i = []
      user_array_list_i.append(i+1)
      user_dict[user_array[i]] = user_array_list_i

q = int(input())

for i in range(q):
      query = list(map(int,input().strip().split()))
      start_index = query[0]
      end_index = query[1]
      k = query[2]

      if user_dict.__contains__(k):
          query_list = user_dict[k]    #通过键值找到这个喜爱程度对应所有的用户id

          count = 0

          for j in range(len(query_list)):
             if start_index <= query_list[j] <= end_index:
                 count += 1

          print(count)
      else:
          print(0)

编辑于 2019-04-10 11:58:28 回复(1)

Python

外表平静内心狂野

#自测通得过，case为0，哪位大佬看看

n=int(input())

list=[]
a,b,c,d,e=map(int,input().split())
list.append(a)
list.append(b)
list.append(c)
list.append(d)
list.append(e)
q=int(input())
count=0
for i in range(q):
l, r, k=map(int,input().split())
for j in list[l-1:r-1]:
if j==k:
count+=1
print(count)
count = 0

发表于 2019-03-23 21:23:48 回复(0)

Python

嘿哈嘿

# 2.20 19:32---19:40
n = int(input())
inp = [int(x) for x in input().split()]
q = int(input())
res = []
for i in range(q):
    arr = [int(x) for x in input().split()]
    res.append(inp[arr[0]-1: arr[1]].count(arr[2]))

for i in range(q):
    print(res[i])
超时，通过率50%

发表于 2019-02-20 19:50:52 回复(0)