首页 > 试题广场 >

用户喜好

[编程题]用户喜好
  • 热度指数：3994 时间限制：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

输入

5
1 2 3 3 5
3
1 2 1
2 4 5
3 5 3

输出

1
0
2

说明

样例解释:
有5个用户，喜好值为分别为1、2、3、3、5，
第一组询问对于标号[1,2]的用户喜好值为1的用户的个数是1
第二组询问对于标号[2,4]的用户喜好值为5的用户的个数是0
第三组询问对于标号[3,5]的用户喜好值为3的用户的个数是2
算法知识视频讲解
添加回答
牛客8046156号头像 牛客8046156号 
#解析：https://blog.csdn.net/weixin_42001089/article/details/87114410
_ = input()
arr = []
 d = {}
 for e in input().split():
 arr.append(int(e))
 d[int(e)] = 0
 n = int(input())
 temp = []
 for i in range(n):
 e = input().split()
 e[0] = int(e[0])-1
 e[1] = int(e[1])-1
 e[2] = int(e[2])
 temp.append(e+[i])
 temp.sort()
 result = []
 left = 0
 right = -1
 arr[0] = 1
 for i in range(n):
 tempList = temp[i]
 left_interval = tempList[0] - left
 right_interval = tempList[1] - right
 for l in range(left_interval):
 d[arr[left+l]]-=1
 for r in range(right_interval):
 d[arr[right+r+1]]+=1
 if tempList[2] in d:
 result.append([d[tempList[2]],tempList[3]])
 else:
 result.append([0,tempList[3]])
 left = tempList[0]
 right = tempList[1]
 result = sorted(result,key = lambda x:x[1])
 for i in range(n):
 print(result[i][0])
编辑于 2019-02-13 14:40:25 回复(1)
C/C++
yang15671头像 yang15671
//提交时间：2020-09-04 语言：C 运行时间： 1572 ms 占用内存：4172K 状态：答案正确

#include <stdio.h>
int main(){
    int n,i,q,l,r,k;    
    scanf("%d",&n);
    
    int like[n];
    for(i=0;i<n;i++){
        scanf("%d",&like[i]);
    }
    scanf("%d",&q);
    for(int j=0;j<q;j++){
        int count=0;            
        scanf("%d%d%d",&l,&r,&k);

        for(int t=l-1;t<r;t++){
            if(like[t]==k){
                count++;                
            }
        }
        printf("%d\n",count);
    }    
    return 0;
}
编辑于 2020-09-04 16:37:12 回复(0)
superpeak头像 superpeak 
if __name__ == '__main__':
    n = int(input())
    st = {}
    arr = list(map(int,input().split()))
    for i in range(n):
        if arr[i] in st:
            st[arr[i]].append(i+1)
        else:
            st[arr[i]] = [i+1]
    q = int(input())
    b = []
    for i in range(q):
        brr = list(map(int,input().split()))
        l,r,k = brr[0],brr[1],brr[2]
        if k in st:
            c = st[k]
            count = 0
            for ci in c:
                if l<=ci<=r:
                    count += 1
            b.append(count)
        else:
            b.append(0)
    for ij in b:
        print(ij)
直接暴力求解是50%，使用倒排的思想，将n的表放入到hash表里，并且为了保存多个值，用list存放index位置。就可以达到100%通过
发表于 2020-08-12 16:31:28 回复(0)
魏洪旭头像 魏洪旭 
_ = int(input().strip())
de_like = list(map(int, input().strip().split()))
q = int(input().strip())
search_data = [] for i in range(q):
    search_data.append(list(map(int, input().strip().split()))) for i in search_data:
    l, r, k = i
    num = 0  print(de_like[l-1:r].count(k))
运行时间超出，那位大神能告知
发表于 2018-08-22 22:33:13 回复(2)
牛客1659416头像 牛客1659416 
#include <iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        int like[n];
        for (int i=0; i<=n-1; i++)
            cin>>like[i];
        int q;
        cin>>q;
        for (int i=0; i<q; i++)
        {
            int l,r,k;
            cin>>l>>r>>k;
            int counts=0;
            for (int j=l-1; j<=r-1; j++)
            {
                if (like[j]==k)
                    counts++;
            }
            cout << counts << endl;
        }
    }
    return 0;
}

编辑于 2018-05-11 16:16:34 回复(7)
小冲冲头像 小冲冲 
/*
1、首先存储的时候，每个喜好值分别一个vector，分别存入map中，对于每个喜好值的vector，存入的是，用户的id，因为输入是从小到大输入的，所以就可以保证vector有序，然后用二分查找区间的左右端点。
2、这里的二分不是常规的二分查找，对于区间左端点，在vector查找的是小于target的点的最大下标，如果target小于vector最小值，直接返回-1
3、对于区间右端点，查找的是小于等于target的最大下标，如果target大于vector的最大值，直接返回vector最大值的下标

*/
#include<iostream>
#include<map>
#include<vector>
using namespace std;


int find_low(vector<int>& v,int target){
    int low=0;
    int high=v.size()-1;
    int mid;
    if(target<=v[low]) return -1;
    if(target>v[high]) return high;
    while(low<high){
        mid=(low+high+1)>>1;
        //cout<<low<<" "<<high<<"  "<<mid<<endl;
        if(target<=v[mid]){
            high=mid-1;
        }else{
            low=mid;
        }
    }
    return high;
}


int find_high(vector<int>& v,int target){
    int low=0;
    int high=v.size()-1;
    int mid;
    if(target<v[low]) return -1;
    if(target>=v[high]) return high;
    while(low<high){
        mid=(low+high+1)>>1;
        //cout<<low<<"  "<<high<<"  "<<mid<<endl;
        if(target==v[mid]){
            return mid;
        }else if(target<v[mid]){
            high=mid-1;
        }else{
            low=mid;
        }
    }
    return high;
}


int main()
{
    int n,q,t;
    map<int,vector<int> > count;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t;
        if(count.count(t)==0){
            vector<int> v;
            v.push_back(i);
            count[t]=v;
        }else{
            count[t].push_back(i);
        }
    }
    cin>>q;
    int l,r,k;
    int sum;
    for(int i=0;i<q;i++){
        cin>>l>>r>>k;
        sum=0;
        if(count.count(k)>0){
            vector<int> v=count[k];
            int low=find_low(v,l);
            int high=find_high(v,r);
            //cout<<low<<" "<<high<<endl;
            sum=high-low;
        }
        cout<<sum<<endl;
    }
    return 0;
}
编辑于 2018-06-08 16:44:37 回复(1)
yr201904050957596头像 yr201904050957596 
# 一个简单的Python实现，输入数据的时候用字典存起来，然后搜索只用去查找字典里的对应项

n = int(input())
user_list = [int(x) for x in input().split()]
q = int(input())
find = [[int(x) for x in input().split()] for _ in range(q)]
 
dic = {}
for i in range(n):
    try:
        dic[user_list[i]].append(i + 1)
    except:
        dic[user_list[i]] = [i + 1]
result_list = []

for i in range(q):
    l, r , k = find[i]
    if k not in dic:
        result = 0
    else:
        
        temp = dic[k]
        result = 0
        if temp[-1] < l or temp[0] > r:
            pass
        else:
            for i in range(len(temp)):
                if l <= temp[i] <= r:
                    result += 1
    
    result_list.append(result)
for r in result_list:
    print(r)
               

发表于 2019-04-14 00:01:03 回复(0)
万事俱备只欠offer头像 万事俱备只欠offer 
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n = in.nextInt();//用户数
        int[] users = new int[n];//用户喜好度
        for (int i = 0; i < n; i++) users[i] = in.nextInt();
        int m = in.nextInt();
        // int[][] da = new int[m][3];
        for (int i = 0; i < m; i++) {

            // for(int j = 0; j < 3; j++){
            int start = (in.nextInt());
            int end = (in.nextInt());
            int p = (in.nextInt());
            int cou = 0;
            // 限时处理，减少空间复杂度，但是也要考虑缓存换页的情况
            for (int k = start - 1; k < end && k < n; k++) {
                // System.out.println("start:" + start + ",end: "+ end + ",k:"+k +",users[p.intValue()]: " + users[k.intValue()]);
                if (users[k] == p)cou++;
            }

            System.out.println(cou);
            // da[i][j] = in.nextInt();

            // }

        }
        // 数据处理完成




    }
}

发表于 2023-10-22 10:27:29 回复(0)
Python
maoxiaomao头像 maoxiaomao 
n=int(input().strip())
like=list(map(int, input().strip().split()))
q=int(input().strip())
A=[]
for i in range(q):
    A.append(list(map(int, input().strip().split())))
for i in range(len(A)):
    print(like[A[i][0]-1:A[i][1]].count(A[i][2]))

发表于 2021-05-26 10:10:24 回复(0)
亲爱的牛牛头像 亲爱的牛牛 
#include <stdio.h>
#include <stdlib.h>
int main(){
    int custom_nums,query_nums,i,j,k;
    int *custom;
    int **query;
    scanf("%d",&custom_nums);
    custom = (int *)malloc(sizeof(int)*custom_nums);
    for(i=0;i<custom_nums;i++){
        scanf("%d",&custom[i]);
    }
    scanf("%d",&query_nums);
    query=(int **)malloc(sizeof(int *)*query_nums);
    for(i=0;i<query_nums;i++){
        query[i]=(int *)malloc(sizeof(int)*3);
        for(j=0;j<3;j++){
            scanf("%d",&query[i][j]);
        }
    }
    for (i = 0;i < query_nums;i++) {
        k = 0;
        for (j = query[i][0]-1;j <= (query[i][1] - query[i][0] + query[i][0] - 1);j++) {
            if (query[i][2] == custom[j]) k++;
        }
        printf("%d\n", k);
    }
    free(custom);
    for(i=0;i<query_nums;i++){
        free(query[i]);
    }
    free(query);
}
发表于 2021-03-07 16:09:53 回复(1)
Couriersix头像 Couriersix
首先观察到用户总数为3e5个，然后查询次数也是3e5，所以直接暴力是不行的。我本来想用线段树维护区间k个数的，但n=3e5连线段树都开不了。实际上这题只要用二分查找就行了，先将原序列中的每一个k在原序列的位置记录到对应的k向量后面，然后查询区间的时候，先判断输入的k是否存在，然后直接lower_bound左边界l和upper_bound右边界r在a[k]中的位置，此时的r1-l1就是答案。最后由于本题没给出k的范围，所以要对原序列的每一个k做离散化处理（具体见代码） 
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
vector<int> a[300005];
int cc[300005],b[300005];
int n,x,q;
int main(){
	cin>>n;
	for (int i=1; i<=n; i++){
		 scanf("%d",&cc[i]);
		 b[i]=cc[i];
		 //a[x].pb(i);
	}
	sort(cc+1,cc+n+1);
	int siz=unique(cc+1,cc+n+1)-cc-1;
    for (int i=1; i<=n; i++){
    	int p=lower_bound(cc+1,cc+1+n,b[i])-cc-1;
    	a[p].pb(i);
	}
	cin>>q;
	int l,r,v,ans,l1,r1;
	while (q--){
		  scanf("%d%d%d",&l,&r,&v);
		  int p=lower_bound(cc+1,cc+1+n,v)-cc-1;
		  if (cc[p+1]!=v){
		  	 cout<<0<<endl;
		  	 continue;
		  } 
		  l1=lower_bound(a[p].begin(),a[p].end(),l)-a[p].begin();
		  r1=upper_bound(a[p].begin(),a[p].end(),r)-a[p].begin();
		  ans=r1-l1;
		  cout<<ans<<endl;
	}
	return 0;
}

发表于 2021-01-23 15:28:46 回复(0)
绿篱头像 绿篱 
user_num = input()
user_like = input().split()
num = int(input())
for i in range(num):
    line = input()
    li = line.split(' ')
    users = user_like[int(li[0])-1:int(li[1])]
    like_num = len([user for user in users if int(user)==int(li[2])])
    print(like_num)
  • python运行时间超出了，咋改
编辑于 2019-08-10 21:26:11 回复(0)
Python
不喝奶茶w头像 不喝奶茶w 
#采用字典
n = int(input())
xihao = list(map(int,input().split()))
dct = {}
for i in range(n):
    if xihao[i] not in dct.keys():
        dct[xihao[i]] = [i]
    else:
        dct[xihao[i]].append(i)

q = int(input())

res = []
for i in range(q):
    l,r,k = list(map(int,input().split()))
    count = 0
    try:
        tmp = dct[k]
        # print(tmp)
        for j in range(len(tmp)):
            if tmp[j] <= r-1 and tmp[j] >= l-1:
                count += 1
    except:
        pass
    res.append(count)

for r in res:
    print(r)

发表于 2019-08-09 14:29:44 回复(0)
算法蛋黄酱头像 算法蛋黄酱

想知道为什么总是本地能过通过，牛客的系统就是出错呢。本地调试看过很多种用例情况应该不出现越界可是报错总是说数组越界。 


	importjava.util.Scanner;





	importjava.util.List;





	importjava.util.ArrayList;





	importjava.util.Arrays;





	public class Main{


public void main(String[] args) {  Scanner input = newScanner(System.in);

Scanner s = newScanner(System.in);

intN = input.nextInt();



List user_list = newArrayList();

List user_like_list = newArrayList();


String sentence = s.nextLine();        

String[] num_pair = sentence.split(" ");


for(inti =0; i<N;i++)

    user_like_list.add(Integer.valueOf(num_pair[i]));


int row = input.nextInt();

for(inti =0; i<row;i++) {

    String like = s.nextLine();        

    String[] like_pair = like.split(" ");

    user_list.add(Integer.valueOf(like_pair[0]));

    user_list.add(Integer.valueOf(like_pair[1]));

    user_list.add(Integer.valueOf(like_pair[2]));

    }


for(inti = 0; i < row;i++) {

    intcount = 0;

    intl = user_list.get(0+ i * 3) - 1;

    intr = user_list.get(1+ i * 3) - 1;

    intk = user_list.get(2+ i * 3);

    for(intj = l;j <= r ;j++) {

        intuser_i_like = user_like_list.get(j);

        if(user_i_like == k)

            count ++;

    }

    System.out.println(count);

}

}

}

编辑于 2019-04-13 02:04:44 回复(0)
C/C++
kirito2018头像 kirito2018 
#include <iostream>
#include <stdio.h>
#include <vector>
 
using namespace std;
int main()
{
    int n;int q;
    while (cin >> n)
    {
        vector<int> score;
        for (int i = 0; i <= n-1; i++)
        {
            int a; cin>>a;
            score.push_back(a);// scanf("%d, &score[i]);
            //不能用 cin>>score[i]; 没有重载
        }
            
        cin>>q;
        for(int i=0; i<q; i++)
        {
            int l,r,k;
            cin>>l>>r>>k;//scanf("%d%d%d", &l, &r, &k);
            int res = 0;
            for(int j=l-1; j<=r-1; j++)
            {
                if(score[j]==k)
                    res++;
            }
            cout<<res<<endl; //printf("%d\n", res);
        }        
    }    
    
    return 0;
}

发表于 2019-03-15 12:39:56 回复(0)
伤逝201808131744503头像 伤逝201808131744503 
 



check_list=[]
user=[]
n = eval(input())
list_n = list(map(int, input().split(' ')))
q = int(input())


for i in range(q):
    a = list(map(int, input().split(' ')))
    user.append(a[:2])
    check_list.append(a[-1])



for j in range(q):
    m = list_n[user[j][0]-1:user[j][1]-1]
    result=m.count(check_list[j])  
    print(result)

编辑于 2019-03-15 10:53:05 回复(1)
Python
算法er头像 算法er 
import bisect
n = int(input())
l = list(map(int, input().split()))
q = int(input())
keys = list(set(l))
score_dict = {}
for k in keys:
    score_dict[k] = []

for i in range(n):
    score_dict[l[i]].append(i)

q_l = []
for q_i in range(q):
    q_l.append(list(map(int, input().split())))
for q_i in range(q):
    l, r, k = q_l[q_i]
    if k in score_dict:
        print(bisect.bisect(score_dict[k], r-1) - bisect.bisect_left(score_dict[k], l-1))
    else:
        print(0)

编辑于 2018-10-29 18:03:44 回复(0)
Python
Marina_Dear头像 Marina_Dear 

	import sys





	n =int(sys.stdin.readline().strip())





	l =map(int, sys.stdin.readline().strip().split())





	m =int(sys.stdin.readline().strip())





	 





	for i in range(m):





	    s =map(int, sys.stdin.readline().strip().split())





	    ind1,ind2,f =s[0]-1, s[1]-1, s[2]





	    a =filter(lambdax: x ==s[2], l[ind1:ind2+1])





	    print len(a)

发表于 2018-09-10 19:04:56 回复(1)
h4nnn头像 h4nnn 
#include <iostream>
#include <stdio.h>
#include <vector>

using namespace std;

int main() {
    int n, q;
    while (cin >> n) {
        vector<int> users(n + 1);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &users[i]);
        }
        cin >> q;
        int l, r, k;
        for (int i = 0; i < q; i++) {
            scanf("%d%d%d", &l, &r, &k);
            int res = 0;
            while (l <= r) {
                res += users[l++] == k ? 1 : 0;
            }
            printf("%d\n", res);
        }
    }
}
编辑于 2018-08-22 17:15:17 回复(0)
Slun夜心头像 Slun夜心
n = int(input()) # 用户数
like = list(map(int,input().strip().split())) # 用户对应喜好度列表
q = int(input()) # 查询组数
inquery = [list(map(int,input().strip().split()))+[i] for i in range(q)]
inquery = [[x[0]-1,x[1]-1,x[2],x[3]] for x in inquery] # 查询组列表
inquery = sorted(inquery,key=lambda x:x[0]) # 按查询组起始位置的大小排序
like_set = set(like)
usernum_dict = dict(zip(like_set,[0]*len(like_set))) # 创建{喜好度:用户数}字典，并初始化每个喜好度对应的用户数
left,right = inquery[0][0],inquery[0][0]-1 # 记录{喜好度:用户数}字典中所统计的用户段起止位置
result = [] # 记录输出结果
for x in inquery:
    for i in range(x[0]-left): # 减去查询组之外已记录的用户数
        usernum_dict[like[left+i]] -= 1
    for i in range(x[1]-right): # 加上查询组之内未记录的用户数
        usernum_dict[like[right+i+1]] += 1
    if x[2] in usernum_dict:
        result.append([usernum_dict[x[2]],x[3]])
    else:
        result.append([0,x[3]])
    left,right = x[0],x[1]
result = sorted(result,key=lambda x:x[1]) # 还原查询组顺序
for x in result:
    print(x[0])
发表于 2018-08-20 22:24:56 回复(0)
提交观点

问题信息

数组 模拟 算法工程师 2018 哈希 字节跳动 查找
上传者：小小
难度：
24条回答 5131浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号