社交网络悄悄关注算法设计与实现-平芜编程栈

1. 题目背景与需求分析

"L2-019 悄悄关注"这道题目来源于程序设计类竞赛，属于社交网络关系处理题型。题目要求我们实现一个能够识别用户"悄悄关注"他人的功能，这在现代社交平台中非常常见。

核心需求可以拆解为：

给定一个用户关注列表和点赞列表
找出那些不在公开关注列表但经常点赞的用户
这些用户即被判定为"悄悄关注"的对象

2. 数据结构设计与选择

2.1 用户关系表示

社交网络中的用户关系通常可以用图结构表示，但本题更适合使用集合和映射：

follow_set = set() # 公开关注的用户集合 like_count = {} # 用户点赞次数字典

选择集合和字典的原因：

集合提供O(1)时间复杂度的成员检查
字典可以高效记录和更新点赞次数
内存占用相对较小，适合大规模数据处理

2.2 阈值参数设计

判断"经常点赞"需要定义一个阈值参数。根据经验值，我们可以设置：

THRESHOLD = 10 # 点赞超过10次视为经常点赞

这个阈值可以根据实际业务需求调整，更科学的做法是使用统计学方法（如Z-score）动态计算。

3. 核心算法实现

3.1 输入数据处理

首先需要正确处理输入数据格式。假设输入格式为：

关注用户数 N 关注用户1 关注用户2 ... 关注用户N 点赞记录数 M 用户A 用户B 点赞次数 ...

处理代码示例：

def process_input(): import sys input = sys.stdin.read().splitlines() n = int(input[0]) follow_set = set(input[1].split()) m = int(input[2]) like_count = {} for line in input[3:3+m]: user_a, user_b, cnt = line.split() like_count[user_b] = like_count.get(user_b, 0) + int(cnt) return follow_set, like_count

3.2 悄悄关注检测算法

核心检测逻辑：

def find_secret_follows(follow_set, like_count, threshold=10): secret_follows = [] for user in like_count: if user not in follow_set and like_count[user] >= threshold: secret_follows.append(user) return sorted(secret_follows) # 按字母序输出

时间复杂度分析：

遍历点赞字典：O(M)
集合成员检查：O(1) per check
排序：O(K log K)，K为结果数量
总体：O(M + K log K)，非常高效

4. 边界情况处理

4.1 特殊输入处理

需要考虑的边界情况：

空关注列表
无点赞记录
重复点赞记录
超大输入规模

改进后的处理代码：

def robust_process_input(): import sys from collections import defaultdict data = sys.stdin.read().splitlines() ptr = 0 try: n = int(data[ptr]) ptr += 1 follow_set = set(data[ptr].split()) if n > 0 else set() ptr += 1 m = int(data[ptr]) ptr += 1 like_count = defaultdict(int) for _ in range(m): if ptr >= len(data): break parts = data[ptr].split() if len(parts) >= 3: user_a, user_b, cnt = parts[0], parts[1], int(parts[2]) like_count[user_b] += cnt ptr += 1 except (ValueError, IndexError) as e: print(f"输入格式错误: {e}") return set(), dict() return follow_set, like_count

4.2 性能优化

对于超大规模数据（如百万级记录）：

使用更高效的数据结构（如C++的unordered_set）
分批处理数据
多线程/多进程处理

5. 完整代码实现

结合上述分析的完整解决方案：

import sys from collections import defaultdict def main(): # 读取输入 data = sys.stdin.read().splitlines() ptr = 0 # 处理关注列表 n = int(data[ptr]) ptr += 1 follow_set = set(data[ptr].split()) if n > 0 else set() ptr += 1 # 处理点赞记录 m = int(data[ptr]) ptr += 1 like_count = defaultdict(int) for _ in range(m): if ptr >= len(data): break parts = data[ptr].split() if len(parts) >= 3: _, user_b, cnt = parts[0], parts[1], int(parts[2]) like_count[user_b] += cnt ptr += 1 # 找出悄悄关注 threshold = 10 secret_follows = [ user for user in like_count if user not in follow_set and like_count[user] >= threshold ] # 按字母序输出 if secret_follows: for user in sorted(secret_follows): print(user) else: print("悄悄关注列表为空") if __name__ == "__main__": main()

6. 测试用例设计

6.1 正常情况测试

输入：

3 Tom Bob Alice 5 John Tom 3 Mike Bob 8 Sarah Alice 12 John Mike 15 Mike Sarah 10

预期输出：

John Mike Sarah

6.2 边界情况测试

无悄悄关注：输入：

2 UserA UserB 1 UserC UserA 5

输出：悄悄关注列表为空

超大输入测试：需要生成包含10万条记录的数据进行压力测试

7. 实际应用扩展

7.1 业务场景延伸

这种算法可以扩展到：

潜在兴趣推荐
社交关系预测
异常行为检测

7.2 算法优化方向

引入时间衰减因子：近期点赞权重更高
多维度分析：结合评论、转发等互动
机器学习模型：预测潜在关注关系

8. 经验总结与注意事项

数据结构选择：集合和字典在这种场景下性能最优
阈值设定：需要根据业务实际调整，可以做成可配置参数
输入处理：务必考虑各种边界情况和错误输入
性能考量：Python在处理超大规模数据时可能性能不足，考虑使用更高效语言实现核心逻辑

一个容易忽略的细节：用户可能既在关注列表又在点赞列表中，此时不应被视为悄悄关注。我们的算法通过先检查关注集合已经正确处理了这种情况。

在实际工程实现中，还可以考虑将结果持久化存储，并添加定期更新机制，以及异常监控等功能，使系统更加健壮可靠。

社交网络悄悄关注算法设计与实现