[编程题]用户喜好

字节跳动题目

链接：https://www.nowcoder.com/questionTerminal/66b68750cf63406ca1db25d4ad6febbf?answerType=1&f=discussion 来源：牛客网

热度指数：9676时间限制：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

Second Try

2020-10-07

直接使用bisect库,但是最后是ridx - lidx, 而不是ridx - lidx - 1还是考虑了好一会儿。

import collections 
import bisect 


n = int(input())
vals = [int(i) for i in input().split()]
col = collections.defaultdict(list)

for idx, val in enumerate(vals):
    col[val].append(idx + 1)

nquestion = int(input())
for _ in range(nquestion):
    lft, rt, val = [int(i) for i in input().split()]
    lidx = bisect.bisect_left(col[val], lft)
    ridx = bisect.bisect_right(col[val], rt)
    # print('lidx, ridx, val',  lidx, ridx, val)
    print(ridx - lidx)
    # r = vals[lft - 1: rt].count(val)
    # print(r)
    

First Try

2020-10-07

使用二分法，找出比left小的和比right大的，允许出现-1和len(arr)的target index出现，然后使用ridx - lidx - 1即可。

有一个问题，这里面的idx是从1开始的，因此一开始构建dict list的时候需要对idx额外加1才行。

import collections 

def bisect_left(arr, target):
    """return idx where arr[idx]<target, idx maybe -1"""
    lft, rt = 0, len(arr) - 1
    while lft <= rt:
        mid = (lft + rt) // 2
        if arr[mid] < target:
            lft = mid + 1
        elif arr[mid] >= target:
            rt = mid - 1
    return rt 

def bisect_right(arr, target):
    """return idx where arr[idx]> target, idx maybe = len(arr)"""
    lft, rt = 0, len(arr) - 1 
    while lft <= rt:
        mid = (lft + rt) // 2
        if arr[mid] <= target:
            lft = mid + 1 
        elif arr[mid] > target:
            rt = mid - 1
    return lft 
  
n = int(input())
vals = [int(i) for i in input().split()]
col = collections.defaultdict(list)

for idx, val in enumerate(vals):
    col[val].append(idx + 1)

nquestion = int(input())
for _ in range(nquestion):
    lft, rt, val = [int(i) for i in input().split()]
    lidx = bisect_left(col[val], lft)
    ridx = bisect_right(col[val], rt)
    # print('lidx, ridx, val',  lidx, ridx, val)
    print(ridx - lidx - 1)
    # r = vals[lft - 1: rt].count(val)
    # print(r)

Failed Try

2020-10-07

超时了，没有使用二分法，直接在列表里查找出现的次数。

其实这题目花费时间最多的是在理解牛客网的输入上面，花费了许久看了答案，才知道这里面的输入输出是怎么回事。

n = int(input())
vals = [int(i) for i in input().split()]
nquestion = int(input())
for _ in range(nquestion):
    lft, rt, val = [int(i) for i in input().split()]
    r = vals[lft - 1: rt].count(val)
    print(r)

运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。 case通过率为50.00%