You are given two arrays of equal length: tweets and timestamps. The i-th tweet was published at time timestamps[i] and contains text tweets[i].
Within the inclusive interval [currentTime - timeWindow, currentTime], find the top at most three hashtags by total number of occurrences.
A hashtag starts with # and continues through consecutive letters, digits, or underscores. Stop the hashtag when any other character is encountered.
Sort the answer by count descending, then lexicographically ascending for ties. Return each hashtag with its leading #.
Function Description
Complete the function topTrendingHashtags in the editor below.
topTrendingHashtags has the following parameters:
String[] tweets: the tweet textsint[] timestamps: publish timesint currentTime: the right end of the windowint timeWindow: the window width ReturnsString[]: the top at most three hashtags in ranked order.
Constraints
1 ≤ tweets.length == timestamps.length ≤ 2 * 10⁵0 ≤ timestamps[i] ≤ 10⁹sum(len(tweets[i])) ≤ 10⁶
Example 1
Input:
tweets = ["hi #a #b", "#a !!!", "no tag", "#b #b"]
timestamps = [1, 2, 3, 4]
currentTime = 4
timeWindow = 2Output:
["#b", "#a"]Explanation:
The active window is timestamps 2 through 4. #b appears twice and #a appears once.
Example 2
Input:
tweets = ["#z #a", "#a", "#z"]
timestamps = [1, 2, 3]
currentTime = 3
timeWindow = 3Output:
["#a", "#z"]Explanation: Both hashtags appear twice, so lexicographical order breaks the tie.
解法
遍历所有推文，仅保留时间窗口 [currentTime - timeWindow, currentTime] 内的推文，按规则扫描提取 hashtag(# 起，连续字母/数字/下划线)，用哈希表统计计数。最后按 (-count, tag) 排序取前 3。复杂度 O(Σ len(tweets[i]))，空间 O(K)，K 为不同 tag 数。
from typing import List
from collections import Counter
def top_trending_hashtags(tweets: List[str], timestamps: List[int],
current_time: int, time_window: int) -> List[str]:
lo = current_time - time_window
counter = Counter()
for tw, ts in zip(tweets, timestamps):
if ts < lo or ts > current_time:
continue
i = 0
while i < len(tw):
if tw[i] == '#':
j = i + 1
while j < len(tw) and (tw[j].isalnum() or tw[j] == '_'):
j += 1
if j > i + 1:
counter[tw[i:j]] += 1
i = j
else:
i += 1
ranked = sorted(counter.items(), key=lambda x: (-x[1], x[0]))
return [tag for tag, _ in ranked[:3]]import java.util.*;
class Solution {
String[] topTrendingHashtags(String[] tweets, int[] timestamps, int currentTime, int timeWindow) {
long lo = (long) currentTime - timeWindow;
Map<String, Integer> cnt = new HashMap<>();
for (int k = 0; k < tweets.length; k++) {
if (timestamps[k] < lo || timestamps[k] > currentTime) continue;
String tw = tweets[k];
int i = 0;
while (i < tw.length()) {
if (tw.charAt(i) == '#') {
int j = i + 1;
while (j < tw.length() && (Character.isLetterOrDigit(tw.charAt(j)) || tw.charAt(j) == '_')) j++;
if (j > i + 1) cnt.merge(tw.substring(i, j), 1, Integer::sum);
i = j;
} else i++;
}
}
List<Map.Entry<String, Integer>> list = new ArrayList<>(cnt.entrySet());
list.sort((a, b) -> a.getValue().equals(b.getValue()) ? a.getKey().compareTo(b.getKey()) : b.getValue() - a.getValue());
String[] ans = new String[Math.min(3, list.size())];
for (int i = 0; i < ans.length; i++) ans[i] = list.get(i).getKey();
return ans;
}
}class Solution {
public:
vector<string> topTrendingHashtags(vector<string>& tweets, vector<int>& timestamps,
int currentTime, int timeWindow) {
long long lo = (long long) currentTime - timeWindow;
unordered_map<string, int> cnt;
for (size_t k = 0; k < tweets.size(); ++k) {
if (timestamps[k] < lo || timestamps[k] > currentTime) continue;
const string& tw = tweets[k];
size_t i = 0;
while (i < tw.size()) {
if (tw[i] == '#') {
size_t j = i + 1;
while (j < tw.size() && (isalnum((unsigned char)tw[j]) || tw[j] == '_')) ++j;
if (j > i + 1) cnt[tw.substr(i, j - i)]++;
i = j;
} else ++i;
}
}
vector<pair<string, int>> v(cnt.begin(), cnt.end());
sort(v.begin(), v.end(), [](auto& a, auto& b) {
return a.second != b.second ? a.second > b.second : a.first < b.first;
});
vector<string> ans;
for (size_t i = 0; i < min((size_t)3, v.size()); ++i) ans.push_back(v[i].first);
return ans;
}
};