算法题：今日头条-用户喜好

发表于 2019-04-11 更新于 2022-09-13 阅读次数：

今日头条2018校招后端方向（第二批）笔试的一道算法题。

题目

为了不断优化推荐效果，今日头条每天要存储和处理海量数据。

假设有这样一种场景：我们对用户按照它们的注册时间先后来标号，对于一类文章，每个用户都有不同的喜好值，
我们会想知道某一段时间内注册的用户（标号相连的一批用户）中，有多少用户对这类文章喜好值为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
2
3

1
0
2

样例解释

样例解释: 有5个用户，喜好值为分别为1、2、3、3、5，

第一组：求 1~2 范围内，喜好值为1的用户总数是多少，结果是 1。

第一组：求 2~4 范围内，喜好值为5的用户总数是多少，结果是 0。

第一组：求 3~5 范围内，喜好值为3的用户总数是多少，结果是 2。

牛客网题目链接

[编程题]用户喜好 - 牛客网

分析

直接遍历有可能会超时。

所以把相同值的用户数据的索引存到一个线性表中，同时根据这个值把所有的线性表都保存在一个 map 中。

然后根据查询范围的索引在用户数据索引中二分查找，然后索引之间相减即可。

解答1[Java]：

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.*;

public class Main {
    public void analyzeClientData() {
        Scanner sc = new Scanner(System.in);
        int dataNum;
        Map<Integer, List<Integer>> data = new HashMap<>();
        int queryNum, l, r, key, hitNum;
        int lowerBound, upperBound;

        dataNum = sc.nextInt();
        for (int i = 1; i <= dataNum; ++i) {
            data.computeIfAbsent(sc.nextInt(), x -> new ArrayList<>()).add(i);
        }

        queryNum = sc.nextInt();
        while (queryNum-- > 0) {
            l = sc.nextInt();
            r = sc.nextInt();
            key = sc.nextInt();
            if (!data.containsKey(key) || l > r) {
                System.out.println(0);
                continue;
            }
            List<Integer> list = data.get(key);
            lowerBound = lowerBound(list, l);
            upperBound = upperBound(list, r);
            hitNum = upperBound - lowerBound;
            System.out.println(hitNum);
        }
    }

    /**
     * @param list
     * @param target
     * @return list 中大于等于 target 的第一个数的索引, 如果不存在则返回 list.size()
     */
    private int lowerBound(List<Integer> list, int target) {
        int first = 0;
        int last = list.size();
        while (first < last) {
            int mid = (first + last) >>> 1;
            if (list.get(mid) < target) {
                first = mid + 1;
            } else {
                last = mid;
            }
        }

        return first;
    }

    /**
     * @param list
     * @param target
     * @return list中大于 target 的第一个数的索引, 如果不存在则返回 list.size()
     */
    private int upperBound(List<Integer> list, int target) {
        int first = 0;
        int last = list.size();
        while (first < last) {
            int mid = (first + last) >>> 1;
            if (list.get(mid) <= target) {
                first = mid + 1;
            } else {
                last = mid;
            }
        }

        return first;
    }

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

代码解释

关于 lowerBound 和 upperBound

首先，lowerBound 和 upperBound 都是 list 中的索引。所以 list 中 [lowerBound, upperBound) 这个区间的用户数据，就从属于总数据的 [l, r] 这个区间。

lowerBound 和 upperBound 相当于是左闭右开的，即 [lowerBound, upperBound)，所以直接用 upperBound - lowerBound 赋值给 hitNum。

computeIfAbsent()

Java 8 中 Map 接口引入的新方法。

当第一个参数看作 key，当 key 不在 map 中时，调用第二个参数，也就是一个方法进行 compute，把第二个参数作为 value，然后把这对 <key, value> 存进 map 中，同时把 value 作为返回值，所以可以在调用这个方法之后在后边调用 add() 方法为 list 添加值。

下标

我在读入数据的时候直接把下标设为从 1 开始，这样后边读入 l 和 r 的时候就不需要进行减 1 了。

测试时候用的 main 方法

解答中的 main() 方法是提交时候用的，测试时候使用的是下边这个。

public static void main(String[] args) {
    File file = new File("test_case_1.txt");
    try {
        FileInputStream fileInputStream = new FileInputStream(file);
        System.setIn(fileInputStream);
    } catch (FileNotFoundException e) {
        e.printStackTrace();
    }
    new Main().analyzeClientData();
}

再分析

如果查询区间，也就是 r - l 普遍很小，那么直接遍历是比较好的方法。

如果喜好值有取值范围的话，可以进一步优化。

假如喜好值取值范围是 010，数据总量为300000时，平均每个喜好值的重复数量为 30000，如果用二分查找，平均查找15次，上下界要查找两次，平均查找30次，如果 r - l 的值小于30，可以选择直接遍历原数据 lr。

空间复杂度的考虑，

一种算法是存进二位数组，而后对二位数组进行排序。但是最初的顺序就乱了。失去了遍历原数据的可能性。

第二种就是直接存在map中的list中，不过也直接失去了遍历原数据的可能性。

补充

C++ 的 STL 中有现成的 lower_bound、upper_bound、equal_range 等函数，位于 <algorithm> 头文件中，如果熟悉 C++，直接用 C++ 写还是很方便的。可以参考这篇文章看看 C++ STL 中是如何实现的。

看牛客上有人说还可以考虑使用莫队算法，可以参考莫队算法学习笔记了解一下莫队算法。

upperBound() 和 lowerBound() 使用的是二分查找，要仔细检查，以防写错。可以参考：

二分查找有几种写法？它们的区别是什么？ - 知乎

细说二分查找 - 52Heartz’s Blog

题目