字节跳动2018校招算法方向之用户喜好
用户喜好
http://www.nowcoder.com/questionTerminal/f0ed5df0a373456a8c9b5a64e6374961
- 开始使用暴力破解法,但运行超时,通过为百分之五十。代码如下:
if __name__ == "__main__": n = int(input()) like = list(map(int,input().split())) q = int(input()) check = [] count = [0 for i in range(q)] for i in range(q): check.append(list(map(int,input().split()))) for i in range(n): #暴力查询 for j in range(q): if like[i] == check[j][2] and i+1 >= check[j][0] and i+1 <= check[j][1] : count[j] += 1 for i in range(q): #输出 print(count[i])
- 由于查找的是在某个区间内的具体一个喜爱度的人数,因此以喜欢度作为关键字,以对这类文章喜爱度为该值的用户标号组成的列表作为键值存到字典中,当查询时,只需要查看k值所对应的列表中在l和r区间内的用户数(bisect模块的特殊功能)即可
import bisect n = int(input()) likes = {} s = list(map(int,input().split())) for i in range(n): if s[i] in likes.keys(): likes[s[i]].append(i+1) else: likes[s[i]] = [i+1] q = int(input()) for line in range(q): l,r,k = map(int,input().split()) count = 0 if k in likes.keys(): indexs = likes[k] l = bisect.bisect_left(indexs, l) r = bisect.bisect_right(indexs, r) count = r-l print (count) else: print (0)