Analyze User Website Visit Pattern
设计题, 给三个array, 分别是用户名, 访问时间和网址. 定义一个3seq是连续3个访问的网址, 求独立用户访问最多的3seq.
这个题超级tricky, 首先要构造3seq, 然后还要注意给的数据不是排序好的, 还要先排序. 最后求3seq的时候,我用”-“作为分隔符来方便给3seq做hash.
|
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 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
class Solution { class Pair { int c; String s; public Pair(String s, int c) { this.s = s; this.c = c; } } class Triple { int t; String s; String w; public Triple(String s, int t, String w) { this.s = s; this.t = t; this.w = w; } } public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) { int n = username.length; List<Triple> t = new ArrayList<>(); for(int i = 0; i < n; i++) { t.add(new Triple(username[i], timestamp[i], website[i])); } Collections.sort(t,(a, b) -> (a.t-b.t)); Map<String, List<String>> map = new HashMap<>(); for(Triple tt : t) { map.putIfAbsent(tt.s, new ArrayList<>()); map.get(tt.s).add(tt.w); } Map<String, Set<String>> countMap = new HashMap<>(); for(Map.Entry<String,List<String>> e : map.entrySet()) { countMap.putIfAbsent(e.getKey(), new HashSet<>()); countMap.get(e.getKey()).addAll(getSeq(e.getValue())); } Map<String, Set<String>> countMapRev = new HashMap<>(); for(Map.Entry<String,Set<String>> e : countMap.entrySet()) { for(String s : e.getValue()){ countMapRev.putIfAbsent(s, new HashSet<>()); countMapRev.get(s).add(e.getKey()); } } List<String> res = new ArrayList<>(); PriorityQueue<Pair> pq = new PriorityQueue<>((a, b) -> (a.c == b.c ? a.s.compareTo(b.s) : b.c - a.c)); for(Map.Entry<String,Set<String>> e : countMapRev.entrySet()) { pq.add(new Pair(e.getKey(), e.getValue().size())); } String ss = pq.poll().s; String[] strs = ss.split("-"); for(String s : strs) res.add(s); return res; } private Set<String> getSeq(List<String> myArray) { Set<String> res = new HashSet<>(); for(int i = 0; i < myArray.size() - 2; i++) { for(int j = i + 1; j < myArray.size() - 1; j++) { for(int k = j + 1; k < myArray.size(); k++) { res.add(myArray.get(i)+"-"+myArray.get(j)+"-"+myArray.get(k)); } } } return res; } } |