首页 > 试题广场 >

用户喜好

[编程题]用户喜好

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

算法知识视频讲解

Java

牛客825905850号

import java.util.*;
public class Main{
public static void main(String []args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int [] arr = new int[n+1];
for(int i = 1;i<=n;i++){
arr[i] = sc.nextInt();
}
int q = sc.nextInt();
for(int j = 0;j<q;j++){
int l =sc.nextInt();
int r =sc.nextInt();
int k =sc.nextInt();
enjoy(arr,l,r,k);
}
}
public static void enjoy(int [] arr,int l,int r,int k){
int count = 0;
for(int m = l;m <= r;m++){
if(arr[m] == k) count++;
}
System.out.println(count);
}
}

发表于 2022-05-01 17:58:24 回复(1)

Java

牛客196305255号

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            Map<Integer,Node> map=new HashMap<>();
           int n=sc.nextInt();
           for(int i=0;i<n;i++){
               int val=sc.nextInt();
               if(map.containsKey(val))
                    map.put(val,map.get(val).add(i+1));
               else
                   map.put(val,new Node(i+1));
           }
           int q=sc.nextInt();
           for(int i=0;i<q;i++){
              int l=sc.nextInt();
              int r=sc.nextInt();
              int k=sc.nextInt();
              if(!map.containsKey(k)){
                  System.out.println(0);
              }else{
                  System.out.println(map.get(k).getSize(l,r));
              }
           } 
       } 
        sc.close();
    }
} 
class Node{
    private TreeSet<Integer> set;
    public Node(int index){
        set=new TreeSet<>();
        set.add(index);
    }
    public Node add(int index){
        set.add(index);
        return this;
    }
    
    public int getSize(int l,int r){
       return set.subSet(l,true,r,true).size();
    }
}

发表于 2021-03-24 20:26:43 回复(0)