首页 > 试题广场 >

用户喜好

[编程题]用户喜好
  • 热度指数：1813 时间限制：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
算法知识视频讲解
添加回答
哈拉哈啦头像 哈拉哈啦 
按喜爱值分类检索即可。

发表于 2019-02-25 21:26:19 回复(0)
WizardBook头像 WizardBook 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int num = input.nextInt();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for(int i = 0; i < num; i++){
            int score = input.nextInt();
            if(!map.containsKey(score)){
                List<Integer> list = new ArrayList<>();
                list.add(i+1);
                map.put(score, list);
            }else{
                List<Integer> list = map.get(score);
                list.add(i+1);
            }
        }
        int time = input.nextInt();
        for(int i = 0; i < time; i++){
            int count = 0;
            int left = input.nextInt();
            int right = input.nextInt();
            int target = input.nextInt();
            List<Integer> list = map.get(target);
            if(list != null){
                int length = list.size();
                for(int j = 0; j < length; j++){
                    int a = list.get(j);
                    if((a >= left) && (a <= right)){
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}

发表于 2022-03-01 02:42:03 回复(0)
Relax__头像 Relax__ 
import java.util.Scanner;

public class Main {
    //查找某个区间对文章的喜爱度为k的人个数
     static int getNum(int[] usr_like, int l, int r, int k) {
        int count = 0;
        for (int i = l; i <= r; i++) {
            if(usr_like[i]==k) count++;
        }
        return count;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] usr_like = new int[n];
        for (int i = 0; i < n; i++) {
            usr_like[i] = sc.nextInt();
        }
        int q = sc.nextInt();
        while (q-- != 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int k = sc.nextInt();
            int ret = getNum(usr_like,l-1,r-1,k);
            System.out.println(ret);
        }
    }
}

发表于 2021-04-11 15:53:01 回复(0)
Java
gonBorn头像 gonBorn 
import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        Map<Integer,ArrayList<Integer>> perfer=new HashMap<>();
        for(int i=1;i<n+1;i++){
            int per=in.nextInt();
            if(perfer.containsKey(per)){
                ArrayList<Integer> list=perfer.get(per);
                list.add(i);
            }
            else{
                ArrayList<Integer> list=new ArrayList<>();
                list.add(i);
                perfer.put(per,list);
            }
        }
        int sel=in.nextInt();
        for(int i=0;i<sel;i++){
            int count=0;
            int start=in.nextInt();
            int stop=in.nextInt();
            int per=in.nextInt();
            if(perfer.containsKey(per)){
                ArrayList<Integer> li=perfer.get(per);
                Iterator<Integer> ltr=li.iterator();
                while(ltr.hasNext()){
                    int num=ltr.next();
                    if(num>=start&&num<=stop){
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
    }
}
改进二楼的代码，遍历列表还是用迭代器效率高
感谢二楼
发表于 2019-03-15 09:56:57 回复(0)
晨风20头像 晨风20
对所用用户，创建map<int 喜爱值，List 喜爱值对应的所有用户升序编号>   O(n）
对于查询的区间编号 [L，R]，在map中查找 喜爱值K，K 对应的用户编号list的区间和 区间[l,r]  有重合部分，计算出区间重合部分用户数即可。

发表于 2018-03-24 12:00:11 回复(1)
zbm来了头像 zbm来了 
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int user = sc.nextInt();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 1; i <= user; i++) {
            int fav = sc.nextInt();
            if (!map.containsKey(fav)) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(fav, list);
            } else {
                List<Integer> list = map.get(fav);
                list.add(i);
            }
        }
        int group = sc.nextInt();
        for (int i = 0; i < group; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int k = sc.nextInt();
            int sum = 0;
            List<Integer> list = map.get(k);
            if (list != null) {
                for (int j = 0; j < list.size(); j++) {
                    if (list.get(j)>=a&&list.get(j)<=b) {
                        sum++;
                    }
                }
            }
            System.out.println(sum);
        }
    }
}

发表于 2019-03-14 12:21:47 回复(1)
洛水流尽千年红尘头像 洛水流尽千年红尘
#include <iostream>
using namespace std;
struct T 
{
    int l;
    int r;
    int k;
};
int main()
{
    int n,m;
    cin >> n;
    int arr[n] = {0};
    for(int i=0;i<n;++i)
    {
        cin >> arr[i];
    }
    cin >> m;
    for(int i=0; i<m; i++)
    {
        T t;
        cin >> t.l >> t.r >> t.k;
        int cnt = 0;
        
        for(int i = t.l ; i<= t.r ; i++)
        {
            if(arr[i-1] == t.k)
            {
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
}
发表于 2019-05-22 20:30:25 回复(0)
desyang头像 desyang
#include "bits/stdc++.h"

using namespace std;

int main() {
    
    int n;
    cin>>n;
    unordered_map<int, vector<int> > mp;
    for(int i = 1; i <= n; i++){
        int d;
        cin>>d;
        mp[d].push_back(i);
    }
    
    int m;
    cin>>m;
    for(int i = 0; i < m; i++) {
        int l, r, k;
        cin>>l>>r>>k;
        int cnt = 0;
        for(auto x : mp[k]) {
            if(x >= l && x <= r) cnt++;
        }
        cout<<cnt<<endl;
    }
    
    
    return 0;
}
发表于 2022-07-10 19:43:46 回复(0)
黎明前夜头像 黎明前夜
为什么我这样写会提示运行超时？运行时间：6001ms
importjava.util.Scanner;
publicclassMain{
    publicstaticvoidmain(String[] args){
        Scanner input = newScanner(System.in);
        intnumber=input.nextInt();
        int[] a=newint[number];
        intvalue;
        for(inti=0;i<number;i++){
            value=input.nextInt();
            a[i]=value;
}
        intl,r,k;
        intgroup_num=input.nextInt();
        for(intj=0;j<group_num;j++){
            l=input.nextInt();
            r=input.nextInt();
            k=input.nextInt();
            intnum=0;
            for(ints=l;s<=r;s++){              
                if(a[s-1]==k){
                    num++;
                }
}
            System.out.println(num);
}
       
}
}
发表于 2022-03-05 10:58:16 回复(1)
AAA感谢信批发小王头像 AAA感谢信批发小王
这题可以对每个喜好度建立一个下标数组。假如现在要查询[l, r, k]，直接在喜好度k对应的数组中对l和r进行二分查找即可。 
import java.util.*;

public class Main {

    Map<Integer, List<Integer>> map = new HashMap<>();

    void solution() {
        Scanner sc = new Scanner(System.in);
        int n, q, l, r, k, x;
        n = sc.nextInt();
        for (int i = 1; i <= n; i++) {
            x = sc.nextInt();
            if (!map.containsKey(x)) {
                map.put(x, new ArrayList<>());
            }
            map.get(x).add(i);
        }

        q = sc.nextInt();
        for (int i = 0; i < q; i++) {
            l = sc.nextInt();
            r = sc.nextInt();
            k = sc.nextInt();
            List<Integer> indexList = map.getOrDefault(k, null);
            if (indexList == null) {
                System.out.println(0);
            } else {
                System.out.println(help(indexList, l, r));
            }
        }
    }

    private int help(List<Integer> indexList, int l, int r) {
        int left = upper(indexList, l);
        int right = lower(indexList, r);
        if (left < 0 || right >= indexList.size()) {
            return 0;
        }
        return right - left + 1;
    }

    private int lower(List<Integer> indexList, int key) {
        int low = 0, hi = indexList.size()-1;
        while (low <= hi) {
            int mid = (low + hi) / 2;
            if (indexList.get(mid) <= key) {
                low = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return low - 1;
    }

    private int upper(List<Integer> indexList, int key) {
        int low = 0, hi = indexList.size()-1;
        while (low <= hi) {
            int mid = (low + hi) / 2;
            if (indexList.get(mid) < key) {
                low = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return hi + 1;
    }

    public static void main(String[] args) {
        new Main().solution();
    }
}


发表于 2021-10-11 23:20:25 回复(0)
进击的蜗蜗牛头像 进击的蜗蜗牛 
// 在第1，2位作者的基础上优化：索引值大于r-1之后可以break跳出循环
public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Map<Integer, List<Integer>> likeMap = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int likeCount = scanner.nextInt();
            if (likeMap.containsKey(likeCount)) {
                likeMap.get(likeCount).add(i);
            } else {
                ArrayList<Integer> list = new ArrayList<>();
                list.add(i);
                likeMap.put(likeCount, list);
            }
        }
        int q = scanner.nextInt();
        int[] result = new int[q];
        for (int i = 0; i < q; i++) {
            int l = scanner.nextInt();
            int r = scanner.nextInt();
            int k = scanner.nextInt();
            List<Integer> ls = likeMap.get(k);
            if (ls == null) {
                result[i] = 0;
                continue;
            }
            Iterator<Integer> iterator = ls.iterator();
            int re = 0;
            while (iterator.hasNext()) {
                Integer next = iterator.next();
                if (next < l - 1) {
                    continue;
                }
                if (next < r) {
                    re++;
                } else {
                    break;
                }
            }
            result[i] = re;
        }
        for (int i = 0; i < q; i++) {
            System.out.println(result[i]);
        }
    }

发表于 2021-08-04 11:07:59 回复(0)
FUTURELYU头像 FUTURELYU 
n = int(input().strip())
like = [int(x) for x in input().strip().split()]
hashmap = {}
for i in range(n):
    if like[i] not in hashmap:
        hashmap[like[i]] = [i+1]
    else:
        hashmap[like[i]].append(i+1)
q = int(input().strip())

for _ in range(q):
    a,b,k = map(int, input().strip().split())
    count = 0
    if k  in hashmap:
        for x in hashmap[k]:
            if x >= a and x <= b:
                count += 1
    print(count)

发表于 2020-04-13 07:55:32 回复(0)
Java
哈哈欣头像 哈哈欣 
  public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);  int peoplenum = sc.nextInt();  Map<Integer, List<Integer>> map = new HashMap<>();  /**  * 输入的时候会出现不同的用户数会出现相同的关注度  * 所以map这样可以自动分出不同关注度分别又多少关注度  */  for (int i = 1; i <= peoplenum; i++) { int guanzhudu = sc.nextInt();  if (!map.containsKey(guanzhudu)) {
                List<Integer> list = new ArrayList<>();  list.add(i);  map.put(guanzhudu, list);  } else {
                List<Integer> list = map.get(guanzhudu);  list.add(i);  }

        } int num = sc.nextInt();//查询组数 //        List<chaxun> list=new ArrayList<>(); //        for (int i=0;i<num;i++){ //            list.add(new chaxun(sc.nextInt(),sc.nextInt(),sc.nextInt())); //        } //        for (int i=0;i<num;i++){ //            int c=Fun(list,i,map); //            System.out.println(c); //        }  /**  * 定义一个查找关注度的循环  * 找到要查找关注度的哪个小组  * 小组中的用户大小要与输入的匹配  */  for (int i = 0; i < num; i++) { int a = sc.nextInt();  int b = sc.nextInt();  int key = sc.nextInt();  int sum = 0;  List<Integer> list = map.get(key);  if (list!=null){ for (int k = 0; k < list.size(); k++) { if (list.get(k) >= a && list.get(k) <= b) {
                        sum += 1;  }
                }
            }
            System.out.println(sum);   }

    }
发表于 2019-10-21 21:26:53 回复(1)
牛客9375725号头像 牛客9375725号 
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<map>
using namespace std;

int main() {
    int n,q,x;
    cin >> n;    
    map<int, vector<int>> map;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        map[x].push_back(i);
    }
    cin >> q;
    int l, r, k;
    for (int i = 0; i < q; i++)
    {
        cin >> l >> r >> k;
        int cnt = 0;
        vector<int> list = map[k];
        for (int j = 0; j < list.size(); j++)
        {
            if (list[j] <= r && list[j] >= l)
                cnt++;
        }
        cout << cnt << endl;
    }
    system("pause");
}
发表于 2019-06-30 12:20:31 回复(0)
夜雨倾城头像 夜雨倾城
***数组，存储输入元素的索引，再通过二分查找数组中的索引
发表于 2018-09-09 00:09:44 回复(0)
Booxz头像 Booxz
因为这道题目中唯一有序的数据是用户编号，所以可以在用户编号上做文章来缩短查询的时间。
为每一个出现的喜爱值添加一个对应的有序的用户编号链表，然后再用折半查找查询人数。
发表于 2018-02-06 21:54:55 回复(0)
提交观点

问题信息

数组 安卓工程师 模拟 2018 哈希 字节跳动 查找
上传者：小小
难度：
16条回答 9539浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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