算法初探LeetCode-推文计数

忘是亡心i 2023-09-26 23:31 7阅读 0赞

### [推文计数][Link 1] ###

一家社交媒体公司正试图通过分析特定时间段内出现的推文数量来监控其网站上的活动。这些时间段可以根据特定的频率（ **每分钟** 、**每小时** 或 **每一天** ）划分为更小的 **时间段** 。

例如，周期 `[10,10000]` （以 **秒** 为单位）将被划分为以下频率的 **时间块** :

*  每 **分钟** (60秒 块)： `[10,69]`, `[70,129]`, `[130,189]`, `...`, `[9970,10000]`
 *  每 **小时** (3600秒 块)：`[10,3609]`, `[3610,7209]`, `[7210,10000]`
 *  每 **天** (86400秒 块)： `[10,10000]`

注意，最后一个块可能比指定频率的块大小更短，并且总是以时间段的结束时间结束(在上面的示例中为 `10000` )。

设计和实现一个API来帮助公司进行分析。

实现 `TweetCounts` 类:

*  `TweetCounts()` 初始化 `TweetCounts` 对象。
 *  存储记录时间的 `tweetName` (以秒为单位)。
 *  `List<integer> getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime)` 返回一个整数列表，表示给定时间 `[startTime, endTime]` （单位秒）和频率频率中，每个 **时间块** 中带有 `tweetName` 的 `tweet` 的数量。
    
     *  `freq` 是 `“minute”` 、 `“hour”` 或 `“day”` 中的一个，分别表示 **每分钟** 、 **每小时** 或 **每一天** 的频率。

**示例：**

输入：
    ["TweetCounts","recordTweet","recordTweet","recordTweet","getTweetCountsPerFrequency","getTweetCountsPerFrequency","recordTweet","getTweetCountsPerFrequency"]
    [[],["tweet3",0],["tweet3",60],["tweet3",10],["minute","tweet3",0,59],["minute","tweet3",0,60],["tweet3",120],["hour","tweet3",0,210]]
    
    输出：
    [null,null,null,null,[2],[2,1],null,[4]]
    
    解释：
    TweetCounts tweetCounts = new TweetCounts();
    tweetCounts.recordTweet("tweet3", 0);
    tweetCounts.recordTweet("tweet3", 60);
    tweetCounts.recordTweet("tweet3", 10);                             // "tweet3" 发布推文的时间分别是 0, 10 和 60 。
    tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 59); // 返回 [2]。统计频率是每分钟（60 秒），因此只有一个有效时间间隔 [0,60> - > 2 条推文。
    tweetCounts.getTweetCountsPerFrequency("minute", "tweet3", 0, 60); // 返回 [2,1]。统计频率是每分钟（60 秒），因此有两个有效时间间隔 1) [0,60> - > 2 条推文，和 2) [60,61> - > 1 条推文。 
    tweetCounts.recordTweet("tweet3", 120);                            // "tweet3" 发布推文的时间分别是 0, 10, 60 和 120 。
    tweetCounts.getTweetCountsPerFrequency("hour", "tweet3", 0, 210);  // 返回 [4]。统计频率是每小时（3600 秒），因此只有一个有效时间间隔 [0,211> - > 4 条推文。
    复制代码

**提示：**

*  0<=time,startTime,endTime<=1090 <= time, startTime, endTime <= 10^90<=time,startTime,endTime<=109
 *  0<=endTime−startTime<=1040 <= endTime - startTime <= 10^40<=endTime−startTime<=104
 *  `recordTweet` 和 `getTweetCountsPerFrequency`，最多有 10410^4104 次操作。

### 思路分析 ###

1 根据每个key进行分组放到对应hashmap中 2 在获取每个freq 的时候计算好区间。 3 使用对应上下界 直接计算上界和下界的元素个数，就是索引差值 4 在区间不存在合理值的时候直接放入0到答案，继续遍历

### 算法代码 ###

Map < String, ArrayList < Integer >> map;
    Map < String, Boolean > issort;
    
    public TweetCounts() {
        this.map = new HashMap < > ();
        this.issort = new HashMap < > ();
    }
    
    public void recordTweet(String tweetName, int time) {
        ArrayList < Integer > integers = map.computeIfAbsent(tweetName, k - > new ArrayList < Integer > ());
        integers.add(time);
        issort.put(tweetName, false);
    }
    
    public List < Integer > getTweetCountsPerFrequency(String freq, String tweetName, int startTime, int endTime) {
        int unit = get(freq);
        ArrayList < Integer > ans = new ArrayList < > ();
        ArrayList < Integer > integers = this.map.get(tweetName);
        if (!issort.get(tweetName)) {
            issort.put(tweetName, true);
            Collections.sort(integers);
        }
        int start = startTime;
        while (start <= endTime) {
            int end = Math.min(start + unit, endTime + 1);
            int right = findupper(integers, end - 1);
            int left = finddown(integers, start);
            if (right == -1 || left == -1) ans.add(0);
            else ans.add(right - left + 1);
            start += unit;
        }
        return ans;
    }
    
    //大于等于 target的最小索引   -1
    int finddown(ArrayList < Integer > arrayList, int target) {
        int a = -1;
        int start = 0;
        int end = arrayList.size() - 1;
        int mid = 0;
        while (start <= end) {
            mid = (start + end) >> 1;
            Integer integer = arrayList.get(mid);
            if (integer >= target) {
                a = mid;
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return a;
    }
    
    //小于等于 target的最大索引   -1
    int findupper(ArrayList < Integer > arrayList, int target) {
        int a = -1;
        int start = 0;
        int end = arrayList.size() - 1;
        int mid = 0;
        while (start <= end) {
            mid = (start + end) >> 1;
            Integer integer = arrayList.get(mid);
            if (integer <= target) {
                a = mid;
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return a;
    }
    
    int get(String fr) {
        if (fr.equals("minute")) return 60;
        if (fr.equals("hour")) return 60 * 60;
        if (fr.equals("day")) return 60 * 60 * 24;
        return -1;
    }
    复制代码

### 结果详情 ###

![format_png][]

### 算法复杂度 ###

*  空间复杂度：O(1)O(1)O(1)
 *  时间复杂度：O(n)O(n)O(n)

在[掘金(JUEJIN)][JUEJIN]一起进步，一起成长！

作者：南巷羽  
链接：https://juejin.cn/post/7226357862967541818

[Link 1]: https://link.juejin.cn?target=https%3A%2F%2Fleetcode.cn%2Fproblems%2Ftweet-counts-per-frequency%2F
[format_png]: https://img-blog.csdnimg.cn/img_convert/ac9713660124383024198671a3235cc7.webp?x-oss-process=image/format,png
[JUEJIN]: https://juejin.cn/user/2168705664158333