link1
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// O(N^3)
class Pair {
int time;
String web;
public Pair(int time, String web) {
this.time = time;
this.web = web;
}
}
class Solution {
static List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, List<Pair>> map = new HashMap<>();
int n = username.length;
// collect the website info for every user, key: username, value: (timestamp, website)
for (int i = 0; i < n; i++) {
map.putIfAbsent(username[i], new ArrayList<>());
map.get(username[i]).add(new Pair(timestamp[i], website[i]));
}
// count map to record every 3 combination occuring time for the different user.
Map<String, Integer> count = new HashMap<>();
String res = "";
for (String key : map.keySet()) {
Set<String> set = new HashSet<>();
// this set is to avoid visit the same 3-seq in one user
List<Pair> list = map.get(key);
Collections.sort(list, (a, b)->(a.time - b.time)); // sort by time
// brutal force O(N ^ 3)
for (int i = 0; i < list.size(); i++) {
for (int j = i + 1; j < list.size(); j++) {
for (int k = j + 1; k < list.size(); k++) {
String str = list.get(i).web + " " + list.get(j).web + " " + list.get(k).web;
// System.out.println("user:"+key+", websites: "+str);
if (!set.contains(str)) {
count.put(str, count.getOrDefault(str, 0) + 1);
set.add(str);
}
if (res.equals("") || count.get(res) < count.get(str) || (count.get(res) == count.get(str) && res.compareTo(str) > 0)) {
// make sure the right lexi order
res = str;
}
}
}
}
}
// grab the right answer
List<String> result = new ArrayList<>(Arrays.asList(res.split(" ")));
return result;
}
}