题目描述
给定两个字符串数组 username 和 website 和一个整数数组 timestamp 。给定的数组长度相同，其中元组 [username[i], website[i], timestamp[i]] 表示用户 username[i] 在时间 timestamp[i] 访问了网站 website[i] 。
访问模式 是包含三个网站的列表(不一定是完全不同的)。
- 例如，
["home"， "away"， "love"]， ["leetcode"， "love"， "leetcode"]，和 ["luffy"， "luffy"， "luffy"] 都是模式。
一种 访问模式 的 得分 是访问该模式中所有网站的用户数量，这些网站在该模式中出现的顺序相同。
- 例如，如果模式是
[“home”，“away”，“love”] ，那么分数就是用户数量 x , x 访问了 “home” ，然后访问了 “away” ，然后访问了 “love” 。
- 同样，如果模式是
["leetcode"， "love"， "leetcode"] ，那么分数就是用户数量 x ，使得 x 访问了"leetcode"，然后访问了 "love" ，之后又访问了 "leetcode" 。
- 另外，如果模式是
[“luffy”，“luffy”，“luffy”] ，那么分数就是用户数量 x ，这样 x 就可以在不同的时间戳上访问 “luffy” 三次。
返回 得分 最大的 访问模式 。如果有多个访问模式具有相同的最大分数，则返回字典序最小的。
示例 1：
输入：username = ["joe","joe","joe","james","james","james","james","mary","mary","mary"], timestamp = [1,2,3,4,5,6,7,8,9,10], website = ["home","about","career","home","cart","maps","home","home","about","career"]
输出：["home","about","career"]
解释：本例中的元组是:
["joe","home",1],["joe","about",2],["joe","career",3],["james","home",4],["james","cart",5],["james","maps",6],["james","home",7],["mary","home",8],["mary","about",9], and ["mary","career",10].
模式("home", "about", "career") has score 2 (joe and mary).
模式("home", "cart", "maps") 的得分为 1 (james).
模式 ("home", "cart", "home") 的得分为 1 (james).
模式 ("home", "maps", "home") 的得分为 1 (james).
模式 ("cart", "maps", "home") 的得分为 1 (james).
模式 ("home", "home", "home") 的得分为 0(没有用户访问过home 3次)。
示例 2：
输入: username = ["ua","ua","ua","ub","ub","ub"], timestamp = [1,2,3,4,5,6], website = ["a","b","a","a","b","c"]
输出: ["a","b","a"]
提示：
3 <= username.length <= 501 <= username[i].length <= 10timestamp.length == username.length1 <= timestamp[i] <= 109website.length == username.length1 <= website[i].length <= 10username[i] 和 website[i] 都只含小写字符- 它保证至少有一个用户访问了至少三个网站
- 所有元组
[username[i]， timestamp[i]， website[i] 均 不重复
解法
方法一：哈希表 + 排序
我们先用哈希表 $d$ 记录每个用户访问的网站，然后遍历 $d$，对于每个用户，我们枚举其访问的所有三元组，统计去重三元组的出现次数，最后遍历所有三元组，返回出现次数最多的、字典序最小的三元组。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^3)$。其中 $n$ 是 username 的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution:
def mostVisitedPattern(
self, username: List[str], timestamp: List[int], website: List[str]
) -> List[str]:
d = defaultdict(list)
for user, _, site in sorted(
zip(username, timestamp, website), key=lambda x: x[1]
):
d[user].append(site)
cnt = Counter()
for sites in d.values():
m = len(sites)
s = set()
if m > 2:
for i in range(m - 2):
for j in range(i + 1, m - 1):
for k in range(j + 1, m):
s.add((sites[i], sites[j], sites[k]))
for t in s:
cnt[t] += 1
return sorted(cnt.items(), key=lambda x: (-x[1], x[0]))[0][0]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 | class Solution {
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, List<Node>> d = new HashMap<>();
int n = username.length;
for (int i = 0; i < n; ++i) {
String user = username[i];
int ts = timestamp[i];
String site = website[i];
d.computeIfAbsent(user, k -> new ArrayList<>()).add(new Node(user, ts, site));
}
Map<String, Integer> cnt = new HashMap<>();
for (var sites : d.values()) {
int m = sites.size();
Set<String> s = new HashSet<>();
if (m > 2) {
Collections.sort(sites, (a, b) -> a.ts - b.ts);
for (int i = 0; i < m - 2; ++i) {
for (int j = i + 1; j < m - 1; ++j) {
for (int k = j + 1; k < m; ++k) {
s.add(sites.get(i).site + "," + sites.get(j).site + ","
+ sites.get(k).site);
}
}
}
}
for (String t : s) {
cnt.put(t, cnt.getOrDefault(t, 0) + 1);
}
}
int mx = 0;
String t = "";
for (var e : cnt.entrySet()) {
if (mx < e.getValue() || (mx == e.getValue() && e.getKey().compareTo(t) < 0)) {
mx = e.getValue();
t = e.getKey();
}
}
return Arrays.asList(t.split(","));
}
}
class Node {
String user;
int ts;
String site;
Node(String user, int ts, String site) {
this.user = user;
this.ts = ts;
this.site = site;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 | class Solution {
public:
vector<string> mostVisitedPattern(vector<string>& username, vector<int>& timestamp, vector<string>& website) {
unordered_map<string, vector<pair<int, string>>> d;
int n = username.size();
for (int i = 0; i < n; ++i) {
auto user = username[i];
int ts = timestamp[i];
auto site = website[i];
d[user].emplace_back(ts, site);
}
unordered_map<string, int> cnt;
for (auto& [_, sites] : d) {
int m = sites.size();
unordered_set<string> s;
if (m > 2) {
sort(sites.begin(), sites.end());
for (int i = 0; i < m - 2; ++i) {
for (int j = i + 1; j < m - 1; ++j) {
for (int k = j + 1; k < m; ++k) {
s.insert(sites[i].second + "," + sites[j].second + "," + sites[k].second);
}
}
}
}
for (auto& t : s) {
cnt[t]++;
}
}
int mx = 0;
string t;
for (auto& [p, v] : cnt) {
if (mx < v || (mx == v && t > p)) {
mx = v;
t = p;
}
}
return split(t, ',');
}
vector<string> split(string& s, char c) {
vector<string> res;
stringstream ss(s);
string t;
while (getline(ss, t, c)) {
res.push_back(t);
}
return res;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39 | func mostVisitedPattern(username []string, timestamp []int, website []string) []string {
d := map[string][]pair{}
for i, user := range username {
ts := timestamp[i]
site := website[i]
d[user] = append(d[user], pair{ts, site})
}
cnt := map[string]int{}
for _, sites := range d {
m := len(sites)
s := map[string]bool{}
if m > 2 {
sort.Slice(sites, func(i, j int) bool { return sites[i].ts < sites[j].ts })
for i := 0; i < m-2; i++ {
for j := i + 1; j < m-1; j++ {
for k := j + 1; k < m; k++ {
s[sites[i].site+","+sites[j].site+","+sites[k].site] = true
}
}
}
}
for t := range s {
cnt[t]++
}
}
mx, t := 0, ""
for p, v := range cnt {
if mx < v || (mx == v && p < t) {
mx = v
t = p
}
}
return strings.Split(t, ",")
}
type pair struct {
ts int
site string
}
|