首页 > 试题广场 >

用户喜好

[编程题]用户喜好

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

算法知识视频讲解

牛客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)

更多回答

哈拉哈啦

按喜爱值分类检索即可。

发表于 2019-02-25 21:26:19 回复(0)

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__

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

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

对所用用户，创建map<int 喜爱值，List 喜爱值对应的所有用户升序编号> O(n）

对于查询的区间编号 [L，R]，在map中查找喜爱值K，K 对应的用户编号list的区间和区间[l,r] 有重合部分，计算出区间重合部分用户数即可。

发表于 2018-03-24 12:00:11 回复(1)

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

#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感谢信批发小王

这题可以对每个喜好度建立一个下标数组。假如现在要查询[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

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);   }

    }