字节青训-小S的倒排索引

问题描述

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

测试样例

样例1：

输入：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]

解题思路：

问题理解

你需要找出两个有序数组 a 和 b 的交集，并将结果按从大到小的顺序返回。

数据结构选择

由于 a 和 b 是有序数组，我们可以利用双指针法来高效地找到交集。
交集的结果需要按从大到小的顺序排列，因此我们可以使用一个 vector 来存储结果，并在最后反转这个 vector。

算法步骤

初始化双指针：分别指向数组 a 和 b 的开始位置。
遍历数组：
- 如果 a[i] 等于 b[j]，则将这个值加入结果集，并移动两个指针。
- 如果 a[i] 小于 b[j]，则移动 a 的指针。
- 如果 a[i] 大于 b[j]，则移动 b 的指针。
反转结果集：由于我们需要从大到小的顺序，最后反转结果集。

最终代码（C++）：

今天终于把c++的判题系统放上去了，后面终于不需要转python了

#include <bits/stdc++.h>
#include <vector>
using namespace std;

vector<int> solution(vector<int>& a, vector<int>& b) {
    vector<int> result;
    int i = 0, j = 0;
    
    // 双指针遍历
    while (i < a.size() && j < b.size()) {
        if (a[i] == b[j]) {
            result.push_back(a[i]);
            i++;
            j++;
        } else if (a[i] < b[j]) {
            i++;
        } else {
            j++;
        }
    }
     reverse(result.begin(), result.end());
    
    return result;
}

int main() {
    vector<int> a1 = {1, 2, 3, 7};
    vector<int> b1 = {2, 5, 7};
    vector<int> res1 = solution(a1, b1);
    cout << (res1 == vector<int>{7, 2}) << endl;

    vector<int> a2 = {1, 4, 8, 10};
    vector<int> b2 = {2, 4, 8, 10};
    vector<int> res2 = solution(a2, b2);
    cout << (res2 == vector<int>{10, 8, 4}) << endl;

    vector<int> a3 = {3, 5, 9};
    vector<int> b3 = {1, 4, 6};
    vector<int> res3 = solution(a3, b3);
    cout << (res3 == vector<int>{}) << endl;

    vector<int> a4 = {1, 2, 3};
    vector<int> b4 = {1, 2, 3};
    vector<int> res4 = solution(a4, b4);
    cout << (res4 == vector<int>{3, 2, 1}) << endl;

    return 0;
}