题目链接

生词篇章查询

题目描述

现有 N 篇文档，每篇文档由若干小写字母单词组成。记第 i 篇文档的单词集合为 （文档编号从 1 开始）。

现给定 M 个查询单词 ，请分别求出每个 所在的文档编号集合。

输入描述:

  • 第一行包含一个整数 N。
  • 接下来 N 行，第 i 行首先给出整数 k_i（该文档的单词数），随后给出 k_i 个单词。
  • 接着一行是一个整数 M（查询次数）。
  • 随后 M 行，每行包含一个查询单词。

输出描述:

  • 对于每个查询单词，输出一行。
  • 按升序序列出所有包含该单词的文档编号，编号间以空格分隔。
  • 若该单词未出现在任何文档中，则输出一个空行。

示例: 输入:

3
5 hello world this is test
4 sample test case data
3 test world data
4
test
data
hello
missing

输出:

1 2 3
2 3
1

解题思路

这是一个典型的构建 倒排索引 (Inverted Index) 的问题。倒排索引是一种数据结构，常用于全文搜索，它将内容（在这里是"单词"）映射到其所在位置的列表（在这里是"文档编号"）。

核心数据结构： 我们需要一个哈希表（Map），它的结构如下：

  • 键 (Key): 单词 (string)
  • 值 (Value): 一个包含该单词的文档编号的集合 (Set)

使用集合 Set作为值有两大好处：

  1. 自动去重: 如果一个单词在同一篇文档中出现多次（如示例2中的"a b a"），集合会自动保证文档编号只被记录一次。
  2. 有序性: 如果我们使用有序集合（如 C++ 的 std::set 或 Java 的 TreeSet），文档编号在插入时就会自动保持升序，省去了最后排序的步骤。

算法步骤:

  1. 建立索引: a. 初始化一个空的哈希表 invertedIndex。 b. 读取文档总数 N。 c. 循环 N 次（docId 从 1 到 N）： i. 读取该行文档包含的单词数 k 和所有单词。 ii. 对于该文档中的每一个单词 word： - 从 invertedIndex 中获取 word 对应的集合。如果 word 是第一次出现，就创建一个新的空集合。 - 将当前的文档编号 docId 加入到这个集合中。
  2. 处理查询: a. 读取查询总数 M。 b. 循环 M 次： i. 读取一个查询单词 queryWord。 ii. 在 invertedIndex 中查找 queryWord。 iii. 如果找到了对应的文档编号集合： - 遍历该集合（此时已自动有序），并按格式打印所有编号。 iv. 如果没有找到： - 输出一个空行。

代码

#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <sstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;
    
    map<string, set<int>> invertedIndex;
    string line;
    getline(cin, line); // Consume the rest of the first line

    for (int i = 1; i <= n; ++i) {
        getline(cin, line);
        stringstream ss(line);
        int k;
        ss >> k;
        string word;
        for (int j = 0; j < k; ++j) {
            ss >> word;
            invertedIndex[word].insert(i);
        }
    }

    int m;
    cin >> m;
    for (int i = 0; i < m; ++i) {
        string queryWord;
        cin >> queryWord;
        if (invertedIndex.count(queryWord)) {
            const auto& doc_ids = invertedIndex[queryWord];
            bool first = true;
            for (int id : doc_ids) {
                if (!first) {
                    cout << " ";
                }
                cout << id;
                first = false;
            }
        }
        cout << endl;
    }

    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        Map<String, NavigableSet<Integer>> invertedIndex = new HashMap<>();
        
        for (int i = 1; i <= n; i++) {
            int k = sc.nextInt();
            for (int j = 0; j < k; j++) {
                String word = sc.next();
                invertedIndex.computeIfAbsent(word, key -> new TreeSet<>()).add(i);
            }
        }
        
        int m = sc.nextInt();
        for (int i = 0; i < m; i++) {
            String queryWord = sc.next();
            Set<Integer> docIds = invertedIndex.get(queryWord);
            
            if (docIds != null && !docIds.isEmpty()) {
                StringJoiner sj = new StringJoiner(" ");
                for (Integer id : docIds) {
                    sj.add(id.toString());
                }
                System.out.println(sj.toString());
            } else {
                System.out.println();
            }
        }
        sc.close();
    }
}

from collections import defaultdict

n = int(input())

# 使用 defaultdict 可以让代码更简洁
inverted_index = defaultdict(set)

for i in range(1, n + 1):
    line = input().split()
    # 第一个元素是单词数量k，可以忽略，直接遍历单词
    words = line[1:]
    for word in words:
        inverted_index[word].add(i)
        
m = int(input())

for _ in range(m):
    query_word = input()
    if query_word in inverted_index:
        # sorted() 保证输出升序
        result = sorted(list(inverted_index[query_word]))
        print(' '.join(map(str, result)))
    else:
        print()

算法及复杂度

  • 算法: 倒排索引 / 哈希表
  • 时间复杂度: ，其中 是所有文档中所有单词的总长度（用于构建索引）， 是所有查询词的总长度（用于查询）。这可以大致看作与总输入大小成线性关系。
  • 空间复杂度: ，其中 是所有唯一单词的总长度， 是单词与文档关联的总数（即 word->docId 映射的总条目数）。