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
| class Solution {
private static class Pair {
int time;
String web;
Pair(int _time, String _web) {
time = _time;
web = _web;
}
}
public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
Map<String, List<Pair>> userPair = new HashMap<>();
for (int i = 0; i < username.length; i++) {
userPair.putIfAbsent(username[i], new ArrayList<>());
userPair.get(username[i]).add(new Pair(timestamp[i], website[i]));
}
String res = "";
Map<String, Integer> patternCount = new HashMap<>();
for (String user : userPair.keySet()) {
List<Pair> pairList = userPair.get(user);
Collections.sort(pairList, (a, b) -> a.time - b.time);
Set<String> patterns = new HashSet<>();
for (int i = 0; i < pairList.size(); i++) {
for (int j = i + 1; j < pairList.size(); j++) {
for (int k = j + 1; k < pairList.size(); k++) {
StringBuilder currPattern = new StringBuilder();
currPattern.append(pairList.get(i).web)
.append(" ")
.append(pairList.get(j).web)
.append(" ")
.append(pairList.get(k).web);
String currPatternString = currPattern.toString();
if (patterns.add(currPatternString)) {
patternCount.put(currPatternString, patternCount.getOrDefault(currPatternString, 0) + 1);
if (res.equals("") || patternCount.get(res) < patternCount.get(currPatternString)
|| (patternCount.get(res) == patternCount.get(currPatternString)
&& res.compareTo(currPatternString) > 0)) {
res = currPatternString;
}
}
}
}
}
}
return Arrays.asList(res.split(" "));
}
}
|
这道题比较坑的就是这个题目描述很迷. 它想表达的意思是, 一个用户按照时间线会visit一些网站. 所有网站构成的非重复combinations(按照时间线不能调换位置)构成一个pattern. 比如[www, aaaa, bbbb, www, aaaa, bbbb]. 那么就能有[www, aaaa, bbbb], [www, aaaa, www]等等. 我们注意到[www, aaaa,
bbbb]这个pattern出现了很多次, 但是我们一个用户只记一次.
然后就是三层for循环遍历所有的combinations.
时间复杂度感觉就是O(n^3)
空间复杂度: O(n^3) n是给定的array的长度. 因为那个存pattern count的会到n^3. 假如给的只有一个用户, 它visit的所有websites都不同. 那组合方式就是Cn3, 也就是n三次方了.
