首页 > 试题广场 >

用户喜好

[编程题]用户喜好

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

勇敢牛牛hh

/**
 * 不知道哪个活雷锋在第15个测试用例里给了个不存在的k，真的是吃了屎。直接到find函数里面加上一个判断吧
 * 如果用传统的线性查找的方法应该会超时
 * 提高速度，可以用hashmap的查找和二分查找，能用二分查找是因为id是递增有序的
 * 把具有相同k值的用户编号用arraylist存储，k和arraylist构成hashmap，
 * 这样一来，k值的查询可以用O（1）的时间
 * 然后获得具有相同k值的用户id列表，用二分查找，注意查找的时候是分左右边界的，给我的l和r不一定在列表里面
 * 如果找不到l，那就返回l后面一个，如果找不到r，就返回r前面一个，做个差就是在[l,r]内的个数了
 */

import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws IOException{
        List<Integer> likes = new ArrayList<>();
        HashMap<Integer,List<Integer>> k_to_likes = new HashMap<>();
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            likes.add(sc.nextInt());
            int index = likes.get(i);
            if (! k_to_likes.containsKey(index)){
                List<Integer> item = new ArrayList<>();
                k_to_likes.put(index, item);
            }
            k_to_likes.get(index).add(i+1);
        }

        int p = sc.nextInt();

        for (int i = 0; i < p; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            int k = sc.nextInt();
            find(k_to_likes, l, r, k);
        }
//        while (sc.hasNextInt() && )
    }
    public static void find(HashMap<Integer,List<Integer>> k_to_likes, int l, int r, int k) throws IOException {
        if (! k_to_likes.containsKey(k)) {
            System.out.println(0);
            return;
        }
        List<Integer> sanme_like = k_to_likes.get(k);
        int count = binary_seatch(sanme_like,r,"right")-binary_seatch(sanme_like,l,"left") + 1;
        System.out.println(count);
    }
    public static int binary_seatch(List<Integer> sanme_like, int target, String position) throws IOException{
        if (sanme_like.isEmpty()) return 0;
        int left = 0, right = sanme_like.size() -1;
        while (left <= right) {
            int mid = left + (right-left)/2;
            if (sanme_like.get(mid) == target) return mid;
            else if (sanme_like.get(mid) > target) {
                right = mid - 1;
            }
            else if (sanme_like.get(mid) < target) {
                left = mid + 1;
            }
        }
        return position.equals("left") ? left : right;
    }

}

编辑于 2022-05-14 14:50:33 回复(0)

Java

克莱登在校生

import java.util.Scanner;
public class Main {
   public static void main(String[] args) {
        outPut();
    }

    public static void outPut() {
        Scanner sc = new Scanner(System.in);
        int userNum = 5;
        userNum = sc.nextInt();

        int[] likeNum =new int[userNum];
        for (int n = 0; n < userNum; n++) {
            likeNum[n]=sc.nextInt();
        }
        int list = 0;
        list = sc.nextInt();
        int[][] select =new int[list][3];// {{1, 2, 1}, {2, 4, 5}, {3, 5, 3}};
        int count = 0;
        for (int k = 0; k < list; k++) {
            select[k][0] = sc.nextInt();
            select[k][1] = sc.nextInt();
            select[k][2] = sc.nextInt();
        }

        for (int[] aSelect : select) {
            for (int m = aSelect[0] - 1; m < aSelect[1]; m++) {
                if (likeNum[m] == aSelect[2])
                    count++;
            }
            System.out.println(count);
            count = 0;
        }
    }
}

顺序查找，超时，只通过了50%的case

编辑于 2018-10-08 16:51:20 回复(0)

Java

一叶之秋~

这个题的主要问题就是使用顺序扫描用户的时候会花费比较长的时间，从而导致超时

为了节省顺序查找的时间，我们可以利用二分查找的思路来实现：
1.使用ArrrayList将喜好值相同的用户id存储起来（此时这个ArrayList的用户id是递增的）
2.使用hashmap将该喜好值为k和对应的用户id的list进行存储
3.每次查找时找到对应k的ArrayList进行二分查找即可

最后可以通过所有测试用例

import java.util.*;
public class Main{
    public int getCount(List<Integer> data, int target){
        int left=0, right = data.size()-1, middle=0;
        while(left <= right){
            middle = left + (right-left)/2;
            if (data.get(middle) > target)
                right = middle-1;
            else if(data.get(middle) < target)
                left = middle+1;
            else
                return middle;
        }
        return left;
    }
     
    public void f(){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextLine()){
            int n, q, l, r, k;
            n = Integer.parseInt(sc.nextLine());
            Map<Integer, List<Integer>> map = new HashMap<>();
            for(int i=1; i<=n; i++) {
                int worth = sc.nextInt();
                if(!map.containsKey(worth))
                    map.put(worth, new ArrayList<>());
                map.get(worth).add(i);
            }
            sc.nextLine();
            q = Integer.parseInt(sc.nextLine());
            for(int i=0; i<q; i++){
                l = sc.nextInt();
                r = sc.nextInt();
                k = sc.nextInt();
                sc.nextLine();
                if(map.containsKey(k)){
                    if(r<map.get(k).get(0) || l > map.get(k).get(map.get(k).size() -1))
                        System.out.println(0);
                    else{
                        int left = getCount(map.get(k), l);
                        int right = getCount(map.get(k), r);
                        if (right < map.get(k).size() && map.get(k).get(right) == r)
                            System.out.println(right-left+1);
                        else
                            System.out.println(right - left);
                    }
                }else
                    System.out.println(0);
            }
        }
    }
     
    public static void main(String[] args){
        new Main().f();
    }
}

编辑于 2018-09-10 10:27:40 回复(2)