Паттерн посещения сайтов с наивысшим рангом

Источник: https://leetcode.com/problems/analyze-user-website-visit-pattern

Даны два строковых массива: username и website, и целочисленный массив timestamp. Все массивы имеют одинаковую длинну, и кортеж [username[i], website[i], timestamp[i]] обозначает, что пользователь username[i]посетил вебсайт website[i] в момент timestamp[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], и ["mary","career",10].
Паттерн ("home", "about", "career") имеет ранг 2 (joe и 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 <= 50
• 1 <= username[i].length <= 10
• timestamp.length == username.length
• 1 <= timestamp[i] <= 109
• website.length == username.length
• 1 <= website[i].length <= 10
• username[i] и[i] состоят из строчных латинских букв.
• Гарантированно существует пользователь, который посетил хотя бы три сайта. И нас не интересуют пользователи, которые посетили 1-2 сайта.
  
• Все кортежи[username[i], timestamp[i], website[i]] уникальны.

Идея решения

1. Создаем кортежи <время, пользователь, сайт> .
   
2. Сортируем кортежи по времени.
   
3. Распределяем кортежи по пользователям, сохраняя сортировку по времени.
4. Если пользователь посетил больше трех сайтов, то генерируем неповторящиеся паттерны, состоящие из 3 элементов, сохраняя сортировку по времени. То есть, если пользователь посетил сайты A, B, C, D, то паттерны будут: {A, B, C}, {A, C, D}, {B, C, D}.
   
5. Считаем ранг каждого паттерна.
   
6. Выбираем паттерн с наивысшим рангом.
   

 

Имплементация

class Solution {
    static class Visit{
        String userName;
        int timestamp;
        String website;
        
        Visit(String u,int t, String w){
            userName=u;
            timestamp=t;
            website=w;
        }
        Visit(){}
    }
    
    public List<String> mostVisitedPattern(String[] username, int[] timestamp, String[] website) {
    
        // Конвертируем массивы в кортежи
        List<Visit> visitList = new ArrayList<>();
        for(int i=0;i<username.length;i++){
            
            visitList.add(new Visit(username[i],timestamp[i],website[i]));
        }
        
        // Сортируем кортежи по времени посещения сайта
        Comparator<Visit> cmp = (v1,v2)->{return v1.timestamp-v2.timestamp;};
        Collections.sort(visitList,cmp);
        
        // Собираем кортежи по пользователям
        Map<String,List<String>> userWebSitesMap= new HashMap<>();
        for(Visit v: visitList){
            userWebSitesMap.putIfAbsent(v.userName, new ArrayList<>());
            userWebSitesMap.get(v.userName).add(v.website);
        }
        
        Map<List<String>,Integer> seqUserFreMap = new HashMap<>();
        // Now get all the values of all the users
        for(List<String> websitesList:userWebSitesMap.values())
        {
        	if(websitesList.size() < 3) continue; // рассматриваем пользователей, посетивших 3+ сайта
            // генерируем послежовательности паттернов
        	Set<List<String>> sequencesSet = generate3Seq(websitesList);
        	// Считаем частоты паттернов
        	for(List<String> seq: sequencesSet)
        	{
        		seqUserFreMap.putIfAbsent(seq, 0);
        		seqUserFreMap.put(seq, seqUserFreMap.get(seq)+1);
        	}
        }
        
        List<String> res= new ArrayList<>();
        int MAX=0; // ищем максимальную частоту
        for(Map.Entry<List<String>,Integer> entry:seqUserFreMap.entrySet()){
        	if(entry.getValue() > MAX){
        		MAX=entry.getValue();
        		res=entry.getKey();
        	}
        	else if(entry.getValue() == MAX){
                // если одинаковые, то выбираем лексикографически меньший элемент
        		if(entry.getKey().toString().compareTo(res.toString()) < 0){
        			res=entry.getKey();
        		}
        	}
        }
        return res;
    }

    // нам не нужны дубликаты паттернов, поэтому используем Set
	private Set<List<String>> generate3Seq(List<String> websitesList) {
		Set<List<String>> setOfListSeq= new HashSet<>();
		for(int i=0;i<websitesList.size();i++){
			for(int j=i+1;j<websitesList.size();j++){
				for(int k=j+1;k<websitesList.size();k++){
					List<String> list = new ArrayList<>();
					list.add(websitesList.get(i));
					list.add(websitesList.get(j));
					list.add(websitesList.get(k));
					setOfListSeq.add(list);
				}
			}
		}
		return setOfListSeq;
	}
}