难度: Medium
Submission
运行时间: 87 ms
内存: 18.9 MB
class Solution:
def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
ct = Counter()
for s in responses:
ct.update(set(s.split()))
return sorted(features, key=lambda x: -ct[x])
Explain
此题解的思路是利用Python内置的collections.Counter类来统计所有响应中各单词出现的次数，然后根据提供的特征列表对特征进行排序。首先，将所有响应分割成单词，并使用set来去除每个响应中的重复单词，确保每个响应对特征的贡献是一次。然后，通过更新Counter对象，对每个特征在所有响应中出现的次数进行统计。最后，使用sorted函数对特征进行排序，排序的关键依据是每个特征的出现次数（从大到小）。
时间复杂度: O(m*k + n log n)
空间复杂度: O(u + k)
class Solution:
def sortFeatures(self, features: List[str], responses: List[str]) -> List[str]:
ct = Counter() # 创建一个计数器来统计每个单词出现的次数
for s in responses: # 遍历每个响应
ct.update(set(s.split())) # 对每个响应分割成单词并去重，然后更新计数器
return sorted(features, key=lambda x: -ct[x]) # 根据特征出现的次数从大到小排序特征列表并返回
Explore
使用`set(s.split())`确实会去除每个响应中的重复单词，这样做的目的是保证每个响应对每个特征的贡献均为一次，避免重复计数。这种做法可能会导致在某个响应中频繁出现的特征的重要性被相对低估。例如，如果一个特征在某个响应中出现多次，这种做法会将其计数为一次，而不是根据实际出现次数。然而，这也避免了个别响应对结果的过度影响，使得统计更加均衡，侧重于特征的普遍重要性而非个别样本中的频繁出现。
在分割单词后立即使用`set`进行去重，是为了确保每个响应中的每个特征只被计算一次，这有助于评估特征在所有响应中的普遍性和重要性。如果在统计完所有响应后再进行去重，会丢失哪些特征在多少个不同响应中出现的信息，只能得到特征的总体出现次数。而题目的目的是要分析特征的广泛相关性，而非仅仅总量，因此，在每个响应处理时立即去重更适合此目的。
在排序时使用`lambda x: -ct[x]`的目的是为了使得排序函数`sorted`能够按照特征出现次数从多到少进行排序。默认情况下，`sorted`函数是按照升序排序的，通过取负值，我们实际上是将原来的递减排序问题转换为递增排序。除此之外，可以使用`sorted(features, key=lambda x: ct[x], reverse=True)`来达到相同的效果，这里通过设置`reverse=True`参数直接指定进行降序排序，避免了取负值的步骤。