青训5_1112_01 小S的倒排索引.md

问题描述

小S正在帮助她的朋友们建立一个搜索引擎。为了让用户能够更快地找到他们感兴趣的帖子，小S決定使用倒排索引。倒排索引的工作原理是：每个单词都会关联一个帖子ID的列表，这些帖子包含该单词，且ID按从小到大的顺序排列。例如，单词“夏天“可能出现在帖子1、帖子3和帖子7中，那么这个单词的倒排链就是［1，3，7]。如果用户想同时找到包含"夏天”和”海滩"的帖子，小S需要找出两个倒排链的交集，且将结果按照从大到小的顺序输出。现在，给定两个单词的倒排链数组a和b，请你帮助小S找出同时包含这两个单词的帖子ID，并按从大到小的顺序返回结果。

测试样例

样例7：
输入：a= ［1，2，3，7，b = ［2，5，7］输出：[7，2］样例2：
输入：a =［1，4，8,10］，b = ［2，4,8,10］输出：［10,8,4］样例3：
输入：a =［3，5,9］，b = ［1，4，6］输出：口样例4：
输入：a = ［1，2,3］，b= ［1，2,3］输出：［3,2,1］

示例

def solution(a, b):# write code herereturn []if __name__ == '__main__':print(solution([1, 2, 3, 7], [2, 5, 7]) == [7, 2])print(solution([1, 4, 8, 10], [2, 4, 8, 10]) == [10, 8, 4])print(solution([3, 5, 9], [1, 4, 6]) == [])print(solution([1, 2, 3], [1, 2, 3]) == [3, 2, 1])

思路

找到两个数据中的相同数字、同时从大到小排序为数组

答案1 内置方法 set(a)& set(b) 及sorted 排序

def solution(a, b):# 将两个列表转换为集合并求交集common = set(a) & set(b)# 将交集转换为列表并降序排序return sorted(list(common), reverse=True)if __name__ == '__main__':print(solution([1, 2, 3, 7], [2, 5, 7]) == [7, 2])print(solution([1, 4, 8, 10], [2, 4, 8, 10]) == [10, 8, 4])print(solution([3, 5, 9], [1, 4, 6]) == [])print(solution([1, 2, 3], [1, 2, 3]) == [3, 2, 1])

方法2 不用内置方法，首席排序和共同数字集合

def solution(a, b):# 用于存储结果的列表result = []# 获取数组长度len_a = len(a)len_b = len(b)# 初始化两个指针，分别指向a和b的起始位置i = 0j = 0# 当两个指针都未到达数组末尾时继续while i < len_a and j < len_b:if a[i] == b[j]:  # 找到相同元素result.append(a[i])i += 1j += 1elif a[i] < b[j]:  # a中的元素较小，移动a的指针i += 1else:  # b中的元素较小，移动b的指针j += 1# 将结果反转，实现从大到小排序left = 0right = len(result) - 1while left < right:result[left], result[right] = result[right], result[left]left += 1right -= 1return result