难度: Medium
Submission
运行时间: 38 ms
内存: 17.2 MB
class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
#user 是key
#如果timestamp逐渐增大，那么可以组成一个合理的元祖 访问模式
#当组成一种合理的模式的时候，可以检查一下在不在这个hashmap里面
#如果在 对应count +1 如果不在那么久把这个模型加进去
userdict=defaultdict(list)
for user, time, web in zip(username,timestamp,website):
userdict[user].append((time,web))
#return userdict
patterndic=defaultdict(set)
def getPattern(user,userInfo,patterndic):
if len(userInfo)<3:
return
elif len(userInfo)==3:
pattern=(userInfo[0][1],userInfo[1][1],userInfo[2][1])
patterndic[pattern].add(user)
else:
len1=len(userInfo)
for i in range(len1-2):
for j in range(i+1,len1-1):
for k in range(j+1,len1):
pattern=(userInfo[i][1], userInfo[j][1], userInfo[k][1])
patterndic[pattern].add(user)
for user in userdict:
userdict[user].sort(key = lambda x : x[0]) #按时间排序
getPattern(user,userdict[user],patterndic)
max_val=0
res=None
for key,value in patterndic.items():
if len(value)>max_val or (len(value)==max_val and (res is None or key < res)):
print(key)
max_val=len(value)
res=key
return res
Explain
这个题解的主要思路是首先根据用户、时间戳和网站信息组成一个以用户为键的字典，其中每个用户对应一个按时间排序的网站访问的列表。之后，对每个用户的访问记录生成所有可能的三元组访问模式，并用一个字典记录这些模式及其对应的不同用户集合。最后，遍历这个模式字典，找出被最多用户访问过的模式。如果有多个模式被相同数量的最多用户访问，则返回字典序最小的模式。
时间复杂度: O(U*n^3 + k*log k)
空间复杂度: O(U*n + k*U)
class Solution:
def mostVisitedPattern(self, username: List[str], timestamp: List[int], website: List[str]) -> List[str]:
# 创建一个字典，以用户为键，存储每个用户的访问记录 (时间, 网站) 列表
userdict=defaultdict(list)
for user, time, web in zip(username,timestamp,website):
userdict[user].append((time,web))
# 创建一个字典，以三元组模式为键，存储访问这些模式的用户集合
patterndic=defaultdict(set)
def getPattern(user,userInfo,patterndic):
# 如果访问记录少于3条，无法形成三元组
if len(userInfo)<3:
return
elif len(userInfo)==3:
pattern=(userInfo[0][1],userInfo[1][1],userInfo[2][1])
patterndic[pattern].add(user)
else:
# 生成所有可能的三元组模式
len1=len(userInfo)
for i in range(len1-2):
for j in range(i+1,len1-1):
for k in range(j+1,len1):
pattern=(userInfo[i][1], userInfo[j][1], userInfo[k][1])
patterndic[pattern].add(user)
# 为每个用户生成模式
for user in userdict:
userdict[user].sort(key = lambda x : x[0]) # 按时间排序
getPattern(user,userdict[user],patterndic)
# 寻找被最多用户访问的模式
max_val=0
res=None
for key,value in patterndic.items():
if len(value)>max_val or (len(value)==max_val and (res is None or key < res)):
max_val=len(value)
res=key
return res
Explore
是的，如果一个用户的访问记录少于3条，这意味着他们的数据不会被考虑在内来形成三元组模式。这样做的合理性在于，生成三元组需要至少三个网站访问记录，否则无法形成有效的三元组序列。此外，忽略这些数据可以减少计算量和简化问题的处理，因为包含少于三个访问记录的用户无法对寻找最常访问模式的任务提供贡献。
在Python中，字典序比较可以直接通过元组比较实现，因为元组的比较是按照字典序进行的，首先比较元组第一个元素，如果相同则比较下一个元素，以此类推。这种比较方法是内建的，非常高效。在题解中，我们保持每个三元组模式为一个元组形式，这样可以直接利用Python的元组比较操作来确保字典序的准确性和比较效率。此方法不需要额外的数据结构或复杂的逻辑，保证了操作的简洁性和执行速度。